Sorting: Selection Sort

Okay, so the first sorting algorithm I will describe is selection sort. This sort is simple to implement, but simple to criticize, as it performs the worst of the three we will discuss. Also perhaps of note is that this is the only non-inherently recursive algorithm, by which I mean that, while it can be implemented recursively, there is little benefit; the recursive algorithm does the same as an iterative one that includes a loop in which the "fenceposts" are moved on each pass through. But I digress—onto the algorithm itself.




Selection sort works by pulling the smallest (or largest, or funniest, or most popular, or whatever criterion the data are being sorted for) item from the list to be sorted, and swapping it with the first (on subsequent passes the i-th) item in the list. This builds a list of sorted data followed by unsorted data. The algorithm terminates when it has performed as many passes as the list is long; then the sorted list has completely replaced the unsorted one.

For an example of how selection sort works, consider the list of integers:
[6, 8, 15, 2, 4, 6],     which we will be sorting in non-descending order.
                        First, we set i=0. 
                             We want to find the least item after i  in the list
                             and swap the i-th item with that one.
                             That item is 2, at index 3. We swap 6 with 2:
[2, 8, 15, 6, 4, 6]     And now we increment i to 1, and repeat, swapping
                             8 with the new minimum:
[2, 4, 6, 15, 8, 6]     Increment and repeat:
[2, 4, 6, 6, 8, 15]     (Notice that above we could have swapped 15 with
                             either 6; which one chosen depends on the specifics
                             of how we find the minimum of the unsorted part.
[2, 4, 6, 6, 8, 15]     Here it looks like we'll do nothing, because the 8
                             and 15 are already in their correct places.                              Nevertheless we still make a pass through, we just
                             don't perform a swap this time, as the minimum is 8
                             itself.
[2, 4, 6, 6, 8, 15]     So here's the final form of the list, sorted in
                            non-descending order.

Selection sort has n-squared complexity—i.e. its runtime scales with the square of the length of the list given it. This is because it makes n, n-1, n-2,...., 1 comparisons on each pass through the list, which sum (by the probably apocryphal yet amusing anecdotal formula) to 0.5 * n * (n+1), a polynomial the degree of which is 2. Selection sort always has this complexity; its performance is not affected by anything other than the length of the list.



Whew, that's all for tonight. Tune in tomorrow for Merge and Quick sort.