Selection Sort

by Mirabelle Jones

If you had a look at bubble sort already (and if you haven’t, I encourage you to have a look), you might be wondering: why did we bother to compare each pair of dolls, one pair at a time? Why didn’t we just search through the whole list to find the the smallest doll, then put that doll at the beginning? We could then repeat this process for the next-to-smallest doll and then the third smallest doll and so on until we build up our sorted list of dolls from shortest to tallest!

In our example, we’re trying to maximize the efficiency of sorting Russian Nesting Dolls (for science!). If we used selection sort, our moves might look as follows. Image from Wikipedia: https://upload.wikimedia.org/wikipedia/commons/thumb/7/71/Russian-Matroshka.jpg/800px-Russian-Matroshka.jpg

This is essentially the concept of selection sort, and again is pretty similar to how most of us might address a sorting problem in the real world! However, like Bubble Sort it’s another somewhat slow and not-so-efficient sorting algorithm. Like Bubble Sort, wee’re learning it because it’s often a good naive solution to explore (say in an interview), it’s pretty easy to understand, it’s foundational for understanding more efficient ways of sorting that we’ll learn about in the upcoming sections!

In Selection Sort, we focus on building up a sorted section at the beginning of our list of numbers (our array) by going through the whole list and relocating the smallest values in order.

Scenario

Let’s return to our Matryoshka (Russian nesting dolls) example from bubble sort and reset our display of Russian nesting dolls to look as follows:

This time, we want to adopt a sorting method where we want to see what the shortest doll is and move it into position 0. We will continue to do this for each doll, again shortening our window of search to exclude dolls we’ve already sort. Each time, we look for the shortest doll and move it to the correct place in order of heights towards the beginning of our array. If this sounds a little confusing, see the following video for an “in action” (and 3D!) example of selection sort:

Selection sort as demonstrated in a future 3D world.

In pseudocode (i.e. not working code), our sort might look like this:

function selectionSortDolls(allDolls){
    for(var doll = 0; doll < allDolls.length; doll++){
        var shortestDoll = doll;
        for(var dollNextdoor = doll+1; dollNextdoor < allDolls.length; dollNextdoor++){
            if(allDolls[dollNextdoor] < allDolls[shortestDoll]){
                shortestDoll = allDolls[dollNextdoor];
            }
        }
        if(doll !== shortestDoll){
      
            var temp = allDolls[doll];
            allDolls[doll] = allDolls[shortestDoll];
            allDolls[shortestDoll] = temp;
        }
    }
    return allDolls;
}

selectionSortDolls([5,0,3,2,7,9,12]);

This is pretty much the procedure we talked about earlier, just put into almost working code. Let’s go through it and have a peek at what’s going on.

As always, we begin by creating our function. It needs to know what we’re sorting and so we feed the function a parameter: the list of our dolls’ heights like so as “allDolls”:

function selectionSortDolls(allDolls){

In our program we’re going to want to go through the dolls one by one or iterate, and so we see that in the following line:

for(var doll = 0; doll < allDolls.length; doll++){

We next declare that our “doll in question” as shortest doll because we want to see whether or not this is true later on in our loop.

var shortestDoll = doll;

Next, we have a for loop in our for loop again, this time for the doll next to the doll we’re examining. This makes sense because we want to make the comparison each time to see if the doll we’re looking at is the shortest. This means for every doll next to our doll, we go through the remaining dolls in the array up until the end!

for(var dollNextdoor = doll+1; dollNextdoor < allDolls.length; dollNextdoor++){

Inside of this loop, we do our actual comparison of our dolls to see which is taller. Is one of the dolls nextdoor shorter than the shortest doll we’ve identified? If so, make this new doll the shortest doll.

 if(allDolls[dollNextdoor] < allDolls[shortestDoll]){
                shortestDoll = allDolls[dollNextdoor];
            }
        }

Now we have identified a shorter doll than the one we thought was the shortest (or not in which case we exit the loop and move down the line). But we still need to swap the dolls if we found a shorter one. We do this on the following lines:

if(doll !== shortestDoll){
      
            var temp = allDolls[doll];
            allDolls[doll] = allDolls[shortestDoll];
            allDolls[shortestDoll] = temp;
        }

This is a swapping construction we saw before in bubble sort. In order to keep track of where our doll was we set a placeholder called “temp.” This just holds the position. Then we can move our doll into the location of shortest doll. Finally we move shortest doll into that placeholder position.

if(allDolls[j] > allDolls[j+1]){

What if we don’t find a shorter doll? Well, we exit the inner loop and go back to our first loop. We leave the doll we’re looking at in the position it is in, then examine the doll next to it. We continue back down the line, doing the whole comparison for the rest of the dolls nextdoor. If we find one that’s shorter, we swap them. And this continues until we have completely sorted our remaining dolls. We “return” the sorted list of dolls which in our case maybe just means we stand back and examine our beautiful sorting work, but to a computer “return” means something else entirely.

 return allDolls;       

If you’d like to learn more about selection sort including how to implement it in real code, check out the sections below.

Big O Complexity

Time Complexity: O(n)^2

Visualizations

Audio-visualization by Timo Bingmann Warning: kinda loud n’ flashy!
Example with cards by Alister Christie

Pseudocode

1. Store the first element as the smallest. 
2. Compare this to the element to every element to the right to see if you can find a smaller one. 
3. If you do find a smaller one, set it as the new smallest! 
4. If the one your started with wasn't the smallest, swap it with your new smallest one.
5. Repeat until sorted. 

Code Examples

Javascript

function sselectionSort(arr){
    for(var i = 0; i < arr.length; i++){
        var lowest = i;
        for(var j = i+1; j < arr.length; j++){
            if(arr[j] < arr[lowest]){
                lowest = j;
            }
        }
        if(i !== lowest){
            //SWAP!
            var temp = arr[i];
            arr[i] = arr[lowest];
            arr[lowest] = temp;
        }
    }
    return arr;
}

selectionSort([13,54,2,15,21,171]);

Sample Problems

Come back soon for these!

More Resources