Sorting (Part 5.0): Selection Sort

[oaktree]

Hello 0x00sec 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

#! /usr/bin/env ruby
 
# just input, ignore
puts "give me a string"
str = gets.chomp.split('')
strlen = str.length
# end of input section, stop ignoring
 
# begin sorting
for i in 0...strlen
    min_pos = i # assume the min element is the first element in the unsorted section of str
 
    for j in i+1...strlen # now loop through str, starting from i+1 since there is no need to reevaluate str[i]
        min_pos = j if (str[j] < str[min_pos]) # update min_pos if we find a smaller element
    end
   
    # now we swap them IF AND ONLY IF the smallest element in the unsorted portion of the array is not in its place yet
    # below you'll see the Ruby syntax for swapping two variables' values... it might look strange, but it actually
    # makes it stupidly simple
    str[i] , str[min_pos] = str[min_pos] , str[i] if min_pos != i
end
 
puts str.join('')

First of all, notice the nested for loops are what makes this algorithm O(n^2).

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

#include <iostream>
#include <string>
#include <vector>
#include <cstdlib>
 
using namespace std;
 
void selectionsort(vector<char>& vec) {
    int n = vec.size();
   
    // start from first element till last
    for (int i = 0; i < n; i++) {
 
        int min_pos = i; // assume first element is the smallest
 
        for (int j = i + 1; j < n; j++) {
            // update position of min element if we find a smaller one
            if (vec[j] < vec[min_pos]) {
                min_pos = j;
            }
        }
 
        // if the minimun is not at position i, we must swap
        if (min_pos != i) {
            int tmp = vec[i];
            vec[i] = vec[min_pos];
            vec[min_pos] = tmp;
        }
    }
}
 
int main() {
    cout << "give me a string" << endl;
    string s; getline(cin, s);
 
    vector<char> vec(s.begin(), s.end());
 
    if (!vec.empty()) selectionsort(vec);
 
    string str(vec.begin(), vec.end());
 
    cout << str << endl;
    return 0;
}

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 ##0x00sec !]) 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!

[Cromical]

Well done