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]); } }