Sorting (Part 5.0): Selection Sort

First and foremost, let me once again apologize for that bug, which I failed to notice in time.

Alright, alright... Enough sulking, oaktree. Get to it!

The Process Behind Selection Sort

Hello NB people! Let's talk about Selection Sort -- oh yeah, I linked Wikipedia!

Selection sort is a lot like Insertion Sort, which -- if you can recall from an earlier post of mine -- involves finding the smallest element in an array and shifting it to one side, proceeding to find the next smallest element, and so on, and so on...

But Selection Sort, in contrast, does not shift over all of the elements; it finds the smallest element a[i], wherever it may be, and swaps it with whichever element currently occupies a[0], unless i == 0.

It goes on to find the next smallest element, excluding the new a[0]. We could call this a[j]. The algorithm swaps this out with a[1] unless j == 1. And this goes on until the elements are all in order.

The algorithm is O(n^2) and O(n). This is the last quadratic complexity sorting algorithm I intend to cover.

Ruby Implementation

Refer to this for the source code of my Ruby implementation of Selection Sort. Alternatively, a screenshot will be provided below.

I skipped down to line 9 in that screenshot because I'm not going to bother discussing the taking of input.

First of all, notice the nested for loops are what makes this algorithm O(n^2) (insert self-hate about for loop bug in Insertion Sort here).

Alright, so we start with the first element, str[0]. And we go ahead and assume that str[0] is the smallest element, because we have yet to see any smaller element in str. But let's only store the position of this minimum element, 0. Thus, we have min_pos = i.

So now we go through the array in the inner for loop looking for a smaller element. We won't start from i because that would just be silly and redundant, since we know that the if condition inside the loop could never evaluate to true when i == j without Divine interference from the Computer Science gods.

If we find a smaller element, let's update min_pos to contain the index of that element. Once we've looped through str, finishing the inner for, we know we've found the smallest element between i and the end of the array (n-1).

If i is not the position of the smallest element in the unsorted portion of str, we must swap str[i] with str[min_pos], meaning we put the smallest element from the still unsorted portion of str (Note: any elements to the left of str[i] make up the sorted portion of str) where it belongs and toss the "original" str[i] in the only available slot, str[min_pos], since that smallest element in the unsorted portion has moved to the sorted portion of the array.

Here's a visual:

And we just keep on with this process until we've gone through the entirety of str, making all of str part of the sorted portion.

C++ Version

Here's the code for my C++ implementation of Selection Sort. And a screenshot awaits below:

It's fundamentally the same as the Ruby code is, semantically.

Peruse the comments, but I feel that there is no point in explaining this code more, since I did a (hopefully) bang-up job up above. Note: what was str in the Ruby code is vec in the C++ code, because I... uh... no reason, really.

Python

I know I said I'd be using Ruby and C++ exclusively for this series, but good guy JSchmoe went and ported the algorithms to Python. You can find his sorty porties (IRC joke [join #nullbyte !]) on pastebin here.

Conclusion

That's it for Selection Sort, the last quadratic complexity sorting algorithm I set out to cover in this series.

'Twas a pleasure,
oaktree

P.S. Quicksort is still to come!