Selection Sort

by kirupa   |   3 January 2015

A slow but very easy-to-comprehend sort algorithm is selection sort. It's approach is very simple. Let's say you have a boring list of values that you want sorted

our initial input

Selection sort works by finding (aka...selecting) the smallest item in your entire list. Once it finds that smallest item, it showers it with love and praise and makes it the first sorted item in a region it carves out called the sorted region. Our selection sort then goes out and finds the next smallest item in the list. Once it finds that item, it places it directly after our earlier smallest item in the sorted region. This whole process of finding the next smallest item and shoving it in the sorted region repeats itself until there are no more unsorted items left.

All of this probably doesn't make a whole lot of sense. It is also boring, so let's fix that with some pictures and stuff in the next section.

Onwards!

Totally Non-Boring Selection Sort Walkthrough

Since I am extremely lazy, let's just continue with the input of bars you saw earlier. Our goal is to use selection sort to sort the bars from shortest to tallest. Along the way, we will also learn a thing or two about how selection sort actually works. Hopefully.

First, putting on our selection sort mask, we are going to assume the first item is the smallest item in the list:

your first item is the smallest...for now

Before you start jumping up and down about the absurdity of this, hold on a second. The next step is to see if the first item is indeed the smallest item in our list. To answer this, selection sort walks through the entire list and compares the size of each item with our current smallest (...and first) item:

are you smaller?

Usually, the first item is rarely the smallest item for long. When selection sort encounters an item that is smaller, this new item becomes the new smallest item. As you can see, this happens immediately in our example, for the next item is smaller than the first item:

the latest small item

At this point, we have a new smallest item. Just like before, though, it is premature to call it a day since we have only examined two values at this point. Our quest to find the smallest number needs to continue, so we compare our newest smallest value with the remaining items in the list to see if another item will take the smallest item crown.

During this trip, you will frequently encounter numbers that are larger than your current smallest value:

a larger item has been found

When that happens, simply skip over it and move on to the next item and repeat the comparison:

the next item

Selection sort will go through the entire list until it has selected the smallest item. For this example, that would be the following bar:

the smallest is found

All that is left is to move this number to the mysterious sorted region that I alluded to earlier, and let's assume that we are going to carve our sorted region from the beginning of our list. To do this, our next step is to swap our smallest item with the first item we started with - the first item in our unsorted region:

swapping the items

Once this happens, your list is partially sorted with the smallest item leading the way. The rest of our list is still unsorted, though:

items swapped

Your sorted region contains one item. Your unsorted region contains everything else. Now, here is where things are going to get a little repetitive and painful...for your computer. We repeat all of what you've seen on the new first item in our unsorted part of the list.

Inside the unsorted world, there is now a new smallest number in town:

the new first number

Just like before, the new smallest number is the first item. As selection sort goes through the unsorted items to find the smallest item, that will change. To be more precise and foreshadowy, it will change to the following bar after all of the unsorted items are examined:

the new smallest number

The next step is for this item to be swapped with our first unsorted item with the sorted region of our list getting one more entry:

you swap stuff and then you do other stuff

This process of finding a new smallest number and swapping it into the sorted region repeats until you have no more unsorted items:

why everything should be sorted

Now, next is where I would normally do a detailed walkthrough using real numbers instead of bars of varying heights. Given how straightforward this algorithm is, let's just skip all that and go to the boring stuff.

Boring Algorithm Schtuff

Selection sort is pretty easy to wrap your brain around. It simply goes through your list of data to find the smallest number, the next smallest number, and so on. Once it finds the smallest number, it places it in what I call the sorted region. There is a lot of flexibility in how you want to implement your sorted region.

Your sorted region could be at the beginning like it was in the examples we've looked at so far:

yes, I re-used an earlier tutorial!

It could also be at the end:

stuff at the end

If you really want to be cray cray, you can use an entirely new list to store your sorted items:

new list

For the most part, given how most list-like data types work in many languages, placing your sorted items at the beginning is straightforward to implement. Placing them at the end or creating an entirely new sorted list requires a little extra effort on your part. Pick whatever makes your life easier. The performance and memory characteristics of all three approaches is pretty similar, so you don't have that to factor those in as part of your decision.

Speaking of performance and memory, selection sort isn't a fast algorithm for sorting your data. Because you pick an unsorted item and compare it against every single other unsorted item, you are doing a whole bunch of comparisons. Basically, it runs in n2 time. From a memory point of view, insertion sort is very good. It doesn't take up much memory beyond any extra objects you need for storing your input itself. That shouldn't be too surprising because almost all of our sorting-related shenanigans are done in-place on the input itself.

The JavaScript Implementation

We are almost done here. The last thing is to look at an example selection sort implementation in JavaScript:

function selectionSort(input) {
  for (var i = 0; i < input.length; i++) {

    // assume the item in the first position is the smallest
    var smallestPosition = i;

    // go through the unsorted region
    for (var j = i + 1; j < input.length; j++) {

      if (input[j] < input[smallestPosition]) {
        // a new smallest number is found
        smallestPosition = j
      }
    }

    // swap the min value if it changed
    if (smallestPosition != i) {
      var temp = input[smallestPosition];
      input[smallestPosition] = input[i];
      input[i] = temp;
    }
  }
}

var myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300];
selectionSort(myinput);

alert(myinput);

The JavaScript doesn't veer too far from the English description you saw in the previous two sections. The outer loop represented by the i variable is responsible for going through each item in the list, and its position marks the dividing line between the sorted region and unsorted region of your input:

where i is

The inner loop represented by the talented j variable is responsible for comparing the item at the outer loop's position with every remaining item in the list. This is the time-consuming and slow part that selection sort is famous for:

the j position

As for other interesting landmarks in our code, the smallestPosition variable stores the position of the smallest item. It starts off as the first item in the unsorted region and then (potentially) changes as the inner loop does the checking against every remaining item in unsorted part of the list.

Once the smallest item has been found, that item gets swapped with the element at the i position. The code for that looks as follows:

if (smallestPosition != i) {
  var temp = input[smallestPosition];
  input[smallestPosition] = input[i];
  input[i] = temp;
}

Just because I am OCD, I do a check to only do the swap if our smallest item is indeed different than the item we started off with. While that doesn't happen often, it is enough to worth adding the check to avoid some unnecessary operations. You can safely skip that if statement if you can sleep well at night without it.

Conclusion

Selection sort makes up the large number of sorts that is easy to understand but not very fast. To see how selection sort compares with other sort algorithms, check out the following table:

Name Best Average Worst Memory
Quicksort n log n n log n n2 log n (average)
Mergesort n log n n log n n log n n (worst case)
Heapsort n log n n log n n log n 1
Timsort n n log n n log n n
Bubble sort n n2 n2 1
Selection sort n2 n2 n2 1
Insertion sort n n2 n2 1

You can find a more detailed comparison of these sorting algorithms as well as many others over on the Wikipedia section fully dedicated to this. If I were you and looking for a slow sort alogirthm that is easy to implement, I would probably choose insertion sort over selection sort any day of the week.

Getting Help

If you have questions, need some assistance on this topic, or just want to chat - post in the comments below or drop by our friendly forums (where you have a lot more formatting options) and post your question. There are a lot of knowledgeable and witty people who would be happy to help you out

Share

Did you enjoy reading this and found it useful? If so, please share it with your friends:

If you didn't like it, I always like to hear how I can do better next time. Please feel free to contact me directly via e-mail, facebook, or twitter.

Kirupa Chinnathambi
I like to talk a lot - A WHOLE LOT. When I'm not talking, I've been known to write the occasional English word. You can learn more about me by going here.

Add Your Comment (or post on the Forums)

blog comments powered by Disqus
Awesome and high-performance web hosting!
BACK TO TOP
new books - yay!!!