Selection sort is a simple and intuitive sorting algorithm. The idea of selection sort is that, it firstly finds the smallest element in the unsorted list and put this element to the end of the sorted list, then it continues to do the same thing until there is no element in the unsorted list, i.e. all elements have been sorted.

The number of comparisons of selection sort is n(n-1)/2, which is the same as that of the bubble sort. However, the worse case number of swaps of selection sort is only n-1, which has better performance than the bubble sort. Recall that the CPU usage for the swaps is more than that for the comparisons, so the selection sort will clearly perform better than the bubble sort when n is large.

Algorithm

Time Complexity
O(n²)

Pseudo Code

selectionSort( Array A[1..n] )
    for( int i := 1..n )
        // find the index of the smallest element
        int indexOfMin = i;
        for( int j := (i+1)..n )
            if( A[indexOfMin] > A[j] )
                indexOfMin = j;
        swap( A[i], A[indexOfMin] );
    return A;