## 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:

*Image via blogspot.com*

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!

## 4 Comments

I like how we can implement things in Ruby with so less number of lines.

Cover quicksort 3 also please :)

Azdan, I plan to cover

aquicksort, but I will probably do some research into quicksort 3aftercovering normal, binary partitioning.Alright.

Each and every sorting techniques i know including quick, insertion, sel, bubble , merge have some limitations.

Which sorting techniques is more efficient in all way.(by efficient i mean fits best)

Is it from the above that i mentioned or is it some other techniques.

## Share Your Thoughts