SelectionSort

SelectionSort is a simple sorting algorithm that makes a number of passes through a list (or sublist) and, on each pass, selects one element to be correctly position. Each element is moved only once; therefore, this type of sort can be handy when sorting files with very large records and small keys.

The item at index 0 is compared with each subsequent item in the list at index 1, 2, ..., N-1. The index of the smallest item encountered is saved. After the comparisons have been completed, the smallest item is swapped with the item at index 0. Repeat this process with index 1, 2, and so on up to N-1.

SelectionSort pseudo-code:

   // assume we have an array 'a' with 'n' elements

   for (cur_i = 0, limit = n-1; cur_i < limit; cur_i++) {
      small_i = cur_i;
      for (next_i = cur_i+1; next_i < n; next_i++) {
         if (COMPARE (a, next_i, small_i))
            small_i = next_i;
      }
      if (small_i != cur_i)
         SWAP (a, cur_i, small_i);
   }

YouTube.com::Selection Sort by CS50 at Harvard