Like Bubble sort, Selection sort is also a comparison based sorting algorithm, but it uses lesser number of swappings. Selection sort works this way. In first iteration it selects the smallest element and keep it in the first place. In the second iteration it selects the next smallest element from the remaining elements and keep it in the second place, and so on.
For example let the input array be [3,1,2,5,4]. Here are the snapshots of the array
in each iteration
[3,1,2,5,4] – smallest element – 1
[1,3,2,5,4] – next smallest element – 2
[1,2,3,5,4] – next smallest element – 3 – no swapping required as it is already in correct position.
[1,2,3,5,4] – next smallest element – 4
[1,2,3,4,5] – Done!
Unlike the bubble sort, selection sort has no mechanism to detect if an array is already sorted. Even if the array is sorted, all iterations are to be completed to fully sort the array.
The following C++ function implements the above technique.
void selection_sort(int *array, int n)
{
int i,j,smallInd;
//outer loop runs for n-1 iterations
for( i = 0 ; i < n-1 ; i++)
{
//assume array[i] is smallest
smallInd = i;
//search for smaller element from index i+1
for( j = i+1; j < n ; j++ )
{
//update if smaller element is found
if( array[j] < array[smallInd])
{
smallInd = j;
}
}
//place the smallest element in its correct position
if( i != smallInd) //dont swap the same elements
swap(array[i],array[smallInd]);
}
}