Selection Sort
(Up to Basic Computer Science : Lists and Arrays : Sorting Algorithms)

Selection Sort is the sort used most often by humans, since it's makes a lot of sense. The algorithm is simple:

Let's say you are sorting some index cards labeled with numbers, and you want to order them smallest to largest. Here are the index cards:

4, 3, 1, 5, 2

Scan the list and find the smallest. This is, of course, 1. Put that into the first position, switching it wih 4. We now have this:

1, 3, 4, 5, 2

Now, we can ignore the 1 and concentrate on the other 4 numbers. Now, we find the next smallest number (which is 2), and move it to the second position. Then we do this for the third smallest, and so on. We keep following this process until we have what we wanted: a sorted list.

On the computer, this algorithm can be consolidated into this form:

For every n, ranging from 1 to the size of the array, start at the nth element of the array and find the smallest element. Switch this element with the nth element of the array.

The concept is quite simple, and therefore makes the algorithm quite easy to program. Even though Selection Sort is one of the slower algorithms, it is used because it sorts with a minimum of data shifting. That is, the algorithm doesn't swap the elements of the array as many times as other algorithms do in order to sort the array. This is really useful when you're programming over a network, because sometimes transferring data can be really slow and time consuming.

Although you should be able to easily program your own version of this simple algorithm, you can study and use the commented version we have in our files:

Download from Source Code Repository: sorts/selection.h