2.4 Selection Sort

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

 Find the smallest element in the list. Swap it with the element in the first position. Repeat step 1 and 2 with all elements except the first one.

Time Complexity
O(n2)

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;`
 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk