COMP1927 - Selection Sort

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

Type

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

Complexity

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.

Example

selection%20%2B%20sort_thumb%5B4%5D.jpg

Code

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