Selection sort is one of the basic algorithms for sorting data, its simplicity proves useful for sorting small amounts of data. Selection sort works by first starting at the beginning array (index 0) and traverses the entire array comparing each value with the current index, if it is smaller than the current index than that index is saved. Once the loop has traversed all the data and if a smaller value than the current index was found a swap is made between the current index in the index where the smaller value was found. The current index is then incremented, now to index 1, the algorithm repeats. Of course, a visual representation is usually more useful. Take an unsorted array that holds five integers.
There are three main variables in selection sort, the variable 'i' keeps the index that may be potentially switched
if a smaller value is found. The variable 'j' traverses through the array searching for a value smaller than 'min'.
The variable 'min' is the current smallest value in the array, it's updated only if a value smaller than it is found.
Since 'min' always receives the value of index 'i' after every iteration, 'j' can begin one more than 'i'. If
index 'j' started at index 'i' then 'min' would be compared with itself obviously there is no need for that. In this
algorithm there are two loops, the first loop containing the 'i' variable the second loop within the first loop contains
the variable 'j'. For example.
void selectionSort(int arr[], int size)
{
for (int i = 0; i < size - 1; i++)//we need to do size-2 passes
{
for (int j = i + 1; j < size; j++)
{
}
}
}
//where size is the number of elements inside the array
Animation of Selection Sort
Source Code of Selection Sort
#include<iostream>
using namespace std;
void selectionSort(int[], int);//Function Prototype
void main() {
int arra[5] = { 3,4,1,2,5 };
selectionSort(arra,
5);
for (int i = 0; i < 5; i++) {
cout
<< arra[i] << endl;
}
}
void selectionSort(int arr[], int size)
{
for (int i = 0; i < size - 1; i++)//we need to do size-2 passes
{
int iMin = i;
for (int j = i + 1; j < size; j++)
{
if (arr[j] < arr[iMin]) {
iMin
= j;
}
}
//swaping
int temp = arr[i];
arr[i] = arr[iMin];
arr[iMin] = temp;
}
}
Output:
0 Questions:
Post a Comment