Selection Sort in a nutshell — how, when & where

knowledge snippets for your next technical test, JavaScript edition

Selection sort is one of the easiest sorting algorithms to understand. In part, because there is minimal complexity. However, simplicity does come with its pitfalls.

Here is a quick low down on what selection sort is, how to write one, when and where you’d most likely encounter it.

How it works

Selection sort has two things going for it — a current minim and a current item.

The current item moves through the array and decides if the it’s smaller than the current minimum. If it is, the current item gets the new marker as the new current minimum.

This process happens right until the end of the array and the marked smallest item will get swapped with the value on the left-hand side. This value becomes partitioned.

The algorithm begins again until all the values are sorted.

In the code

If we were to turn this into pseudo-code, it’ll look something like this:

for(j=0; j<n-1;j++)
int currentMin = j;
for(i=j+1;i<n;i++)
if(arrayList[i] < arrayList[currentMin])
currentMin = i;
if(currentMin != j)
swap(arrayList[j], arrayList[currentMin]);

Let’s translate this code into picture form so you can see how it’s applied.

the first part of the algorithm
the second part of the algorithm
The final part of the algorithm for this particular round.

So what does it look like in JavaScript?

Here’s a piece of code for a simple array that implements selection sort.

function selectionSort(yourArray){let arrSize = yourArray.length;
let currentMin;for (i=0; i < arrSize; i++){//set minimum to this position
currentMin = i;//check the rest of the array to see if anything is smaller
for (j=i+1; j < arrSize; j++){
if (yourArray[j] < yourArray[currentMin]){
currentMin = j;
}
}//if the minimum isn't in the position, swap it
if (i != currentMin){
var temp = yourArray[i];
yourArray[i] = yourArray[currentMin];
yourArray[currentMin] = temp;

}
}return yourArray;
}

The above code is a translation of the pseudo-code and runs two sets of for loops and you’ll need to modify it for your own data if its a map.

The pros and cons

Selection sort is one of the easiest algorithms to understand. However, it comes with it pitfalls.

Selection sort is one of the slowest algorithms and can fall behind bubble sort. But slow doesn’t always mean its bad in all potential cases, often being the last to finish sorting for large arrays. However, it does work very well on small lists.

Selection sort can be good at checking if everything is already sorted. It is also good to use when memory space is limited. This is because unlike other sorting algorithms, selection sort doesn’t go around swapping things until the very end, resulting in less temporary storage space used.

Final words

So that’s selection sort. Sorting algorithms is often one of the things that have a high chance of cropping up in technical tests, so be sure to know how they work, even if you don’t end up using them in your projects.

The purpose of technical tests is to check your awareness of algorithms, which in turn deals with data — and everything boils down to data if you think about it.

So that’s it for this piece. Thank you for reading and I hope you’ve found the diagrams and animation useful.

Report

What do you think?

Leave a Reply

Your email address will not be published. Required fields are marked *

Loading…

0

Comments

0 comments

The Low Down on Attribute and Structural Directives in Angular

So You’re Self-Taught, Now What?