Sunrise in the fog

    Selection Sort

    After seeing CodePen do a month on algorithms for its #codepenchallenges (specifically the challenge for Bubble Sort) I decided I wanted to go over many of the different sorts in a series of posts. I'll be starting with another of the more basic sorts, the selection sort (if the title didn't make that abundantly clear).

    The principle of the selection sort is fairly straightforward - possibly even more so than the bubble sort. Starting at the first index, we'll find the smallest number that occurs starting at that index and moving to the end of the array. If it is smaller than the first number (i.e. it's not the number we started on), we'll swap them. We then move on to the second number. Loop through everything after it, finding the lowest number that occurs after it, and then swap if we need to. We'll do this until we reach the end of the array. Essentially, we loop over the array and select the lowest number, then loop over and select the next lowest number. Hence, the name of the sort.

    Here's an example (in JavaScript):

    [gist src=https://gist.github.com/benrgreene/d538e687bd1f0e068ae0d2985b383c48 file=selection-sort.js][/gist]

    As we can see, not a whole lot of code; and not a lot going on here. What we should take note of though, is the complexity of the sort in terms of the efficiency of the algorithm.

    Specifically I'd like to draw attention to the nested loops. Right there we know our worst case is O(n^2) if we go through the totality of both the outer loop and the inner loop each time it's run. But we also notice that there's no break or escape from the inner loop... meaning that our best case is actually the same as our worst case, O(n^2).

    That's not the greatest best case. It's actually one of the worst best case scenarios there is in the world of sorting algorithms. With this sort we've traded efficiency for simplicity. Which means that if we aren't sorting large arrays it's a pretty solid choice; if we are then we should find something else.

    There you go, the selection sort! I'll cover some more sorts in the coming weeks, but here's a good start to the series.