COMP1927 - Selection Sort

Selection Sort has a very simple algorithm; find the smallest and swap it with the first unsorted element. Rinse and repeat.


Stable (although really it can be unstable, if you set it to smallest if it's less than or equal to


Selection sort has a best, worst and average complexity of O(n2), as it has no early entry and always traverses the list (of n elements) n times.

However it only performs n swaps, one for each element.




void selectionSort (int array[], int length) {
   // While the list isn't sorted
   int i;
   int unsortedStart;
   int smallest;
   int smallestCell;
   int temp;
   for (unsortedStart = 0; unsortedStart < length; unsortedStart++) {
      // Traverse the list to find the smallest item      
      smallest = array[unsortedStart];
      smallestCell = unsortedStart;
      for (i = unsortedStart; i < length; i++) {
         if (array[i] < smallest) {
            smallest = array[i];
            smallestCell = i;
      // Swap the smallest with the first item of the unsorted list
      temp = array[smallestCell];
      array[smallestCell] = array[unsortedStart];
      array[unsortedStart] = temp;