Photo by Victoriano Izquierdo on Unsplash

Searching and Sorting algorithms in Javascript — Part 3 (Selection Sort)

Another very common sorting algorithm you should know about is the Selection Sort algorithm. It is also very easy to implement. Without taking much of your time, let’s get into how this works.

Given an array of numbers — [10, 8, 11, 1, 3, 80, 2, 7, 9], our selection sort function will take this array and return the following — [1, 2, 3, 7, 8, 9, 10, 11, 80]. The aim is to sort the array from lowest to highest so, let’s take a look at the steps involved:

1. We loop through the array of numbers from start to finish (we’ll call this L1)
2. On each loop, we take the number at the current index i and save it somewhere.
3. We’ll start another loop within our initial loop (L1) which will loop over our array of numbers from i+1 to the end of the array. Let’s call this loop L2.
4. We’ll then compare our current number in L1 to each number in L2. We’ll be on the lookout for all numbers smaller than our current number in L1, take the smallest of those numbers (smallest of the smallest) and swap it with our current number in the original array. This will place the current number in L1 in the proper position. This means that by the end of each pass in L1, all numbers to the left are sorted.
5. Repeat this for all numbers in L1. By the time we get to the end of the loop in L1, all numbers will have been sorted.

I understand this might sound gibberish right now but, let’s see this in code. Shall we??

Implementation of the selection sort algorithm.

How is this any better than Bubble Sort?

The main difference between bubble sort and selection sort is that the bubble sort operates by repeatedly swapping the adjacent elements if they are in the wrong order while the selection sort arranges the element of an array by repeatedly finding the minimum element from the unsorted part and placing that at the beginning of the unsorted part.

Another major difference is that Selection sort tend to be faster and more efficient than bubble sort. Although, they both have a worst case time complexity of O(n^2), selection sort still appears to be faster in most cases. This is due to the number of swaps performed in selection sort compared to bubble sort.

Personally, for small arrays ( _insert your definition for “small arrays”_), I’ll choose selection sort over bubble sort.

I hope that explains selection sort for you. If you still need more clarification, checkout this visual representation of selection sort at Visualgo — https://visualgo.net/en/sorting.

See you on the next one!