Selection sort

Selection sort is one of the simplest sort algorithms, but also one of the slowest. It is really only usable with very small data sets. It works by finding the smallest element in the array and placing it at the start. It then finds the 2nd smallest element and places it in the 2nd position. This continues until the entire array has been sorted.

For the algorithm to work, it must ignore elements that have already been sorted. For instance, once you have placed the smallest element in its correct position (ie at the start), you must ignore it for the rest of the sort. In practice this means that to implement the algorithm, you skip the items you have already sorted, looking only for the smallest element that is not yet sorted.

One thing to note is that the selection sort's speed is constant for a given number of elements. It is not affected by presorted or random data, thus implementing a shell sort with a selection sort does not improve the speed.

Implementing a selection sort is easy:

  1. Examine each element in the list to find the smallest.
  2. Swap the element found in step 1 with the first element in the list
  3. Repeat steps 1 and 2, each time ignoring the element at the start of the last sort. Stop when you have only one element to sort.