I’m still working my way through implementing the basic sorting algorithms in Ruby, so maybe I should just make this a special “Intro Sorting Week.” There, sounds like a fun holiday, right? Today we’re talking selection sort.

Selection Sort

Selection sort is where you scan the array, pick the smallest element, and then swap it with the first element. Then you scan the rest of the array again, look for the next smallest element, and then swap it with the second element… Y’all see where I’m going with this?

It creates a sorted subarray on the left, and an unsorted subarray on the right. You work your way through smaller and smaller subarrays until the entire array is sorted. The algorithm is called selection sort because it repeatedly SELECTs the next smallest element and swaps it into place.

A common example of real life selection sort is when you’re playing cards and you are organizing your hand. You look over your hand, and SELECT a card and move it to its rightful place on the left (creating a sorted section), and continue working through until your hand is sorted. To me this isn’t the greatest example, because you’re not necessarily swapping the items when you select and sort a minimum card. It’s more like the cards are individually going both left and right, and often you can move multiple cards at a time. But that’s just me and how I organize my cards… back to Selection Sort.

The good: Selection sort is easy to understand. It’s also faster than bubble sort, but given how awful BS is (ever notice that bubble sort is BS?) that’s not much of an accomplishment. Selection sort is also in place, so it saves you space.

Downsides: This sorting algorithm takes a long long time. O(n^2) even in its best case. Ouch! Also it’s important to note that it’s not stable.

Here’s my selection sort done with two for loops: