# Sorting (Part 5.0): Selection Sort

(oaktree) #1

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!

2 Likes

#2

Well done

0 Likes

(oaktree) closed #3

This topic was automatically closed after 30 days. New replies are no longer allowed.

0 Likes