Selection Sort

Again, see the instruction step following this video for code to implement this algorithm in various languages!

Previously, we showed you Bogosort, a terrible sorting algorithm that basically randomizes the order of a list and then checks to see if it happens to be sorted. The problem with Bogosort is that it doesn't get any closer to a solution with each operation, and so with lists that have more than a few items, it will probably never finish sorting them.

Now we're going to look at an algorithm named Selection Sort. It's still slow, but at least each pass through the list brings it a little closer to completion.

Our implementation of selection sort is going to use two arrays, an unsorted array and a sorted one. (Some versions move values around within just one array, but we're using two arrays to keep the code simpler.) The sorted list starts out empty, but we'll be moving values from the unsorted list to the sorted list one at a time. With each pass, we'll look through each of the values in the unsorted array, find the smallest one, and move that to the end of the sorted array.

Suppose our unsorted list looks like this:

[8, 5, 1, 4, 7]

We'll start with the first value in the unsorted array, and say that's the "minimum", or smallest, value we've seen so far. Then we'll look at the next value and see if that's smaller than the current minimum. If it is, we'll mark that as the new minimum. Then we'll move to the next value and compare that to the minimum again. If it's smaller, that becomes the new minimum. We continue that way until we reach the end of the list. At that point, we know whatever value we have marked as the minimum is the smallest value in the whole list.

Now, here's the part that makes selection sort better than Bogosort: we then move that minimum value from the unsorted list to end of the sorted list. The minimum value isn't part of the unsorted list anymore, so we don't have to waste time looking at it any more. All our remaining comparisons will be on the remaining values in the unsorted list.

Then we start the process over. At this point, our list consists of the numbers [8, 5, 4, 7]. Our first minimum is 8. We start by comparing the minimum to 5. 5 is smaller than 8, so 5 becomes the new minimum. Then we compare 5 to 4, and 4 becomes the new minimum. 4 is not smaller than 7, though, so 4 remains the minimum. 4 gets moved to the end of the sorted array, becoming its second element.

The process repeats again: 8 is the first minimum, but 5 is smaller so that becomes the new minimum. 7 is larger so 5 stays as the minimum, and 5 is what gets moved over to the sorted array.

And so on, until there are no more items left in the unsorted array, and all we have left is the sorted array.

The movement of numbers from "unsorted" to "sorted" will look like this.

Unsorted        Sorted
[8, 5, 1, 4, 7] []                                                                                      
[8, 5, 4, 7]    [1]                                                                                     
[8, 5, 7]       [1, 4]                                                                                  
[8, 7]          [1, 4, 5]                                                                               
[8]             [1, 4, 5, 7]                                                                            
[]              [1, 4, 5, 7, 8]