Sorting Algorithms : Selection Sort

(Javascript implementation)

Selection Sort Algorithm

Time Complexity :

Worst Case : O(n²)
It could be slightly better than “Bubble Sort” in case that you want to minimize the swaps.

How it works :

Contrary to Bubble Sort, this algorithm will start sorting the elements towards the beginning of the array instead of the end.

To accomplish that it needs to create a variable where it will be storing the lowest value and comparing with the rest of the elements.

If during the iteration finds a lower value, it will update our variable so when the iteration is done, the lowest value will swap with the first index of that iteration.

In order two swap the items let’s reuse the swap function that we created for the Bubble Sort Algorithm.

It will repeat the whole operation until the array is sorted.

Let’s visualize the algorithm:

Let’s start our first iteration from the first index. Currently 5 is our lowest stored value.
We move forward and compare 4 with our current lowest value. Since is less than5, 4 becomes our new lowest value.
The same happens wen we move forward and compare 1 with the lowest value.
1 sill being the lowest, so we don’t update the lowest value with 2.
We move until the last element of the array. 1 still being the lowest one.
We swap the lowest value with the first index on the current iteration and then we start to iterate again. This time from the next element of the array.
Let’s repeat the process. 4 is stored as the lowest value so we just move forward.
2 is lower than 4 so it replaces it.
We move to the end, and 2 still the lowest one, so we will swap it with the 1st element of the current iteration (remember, this time we started from 4)
Let’s repeat the process starting now from the next index of the array. In this case, 5.
4 is less than 5 so it becomes our new lowest.
3 is lower than 4 and also the last element. Time to swap with the current first element of the iteration, 5.
Let’s start again the process from the next element, 4.
Since there is nothing to swap and the array is sorted we just move forward.
And… our array is sorted!

Swap helper function :

For more info about how this function works, please check Bubble Sort.

Pseudocode :

// Store in a variable the index of the smallest value so far.// Iterate over the array comparing the elements with the smallest  
value.
// If a smaller value is found, replace the variable with the new
element.
// Iterate until the end of the array and swap the lowest found
value.
// If the "smaller" is not the value (index) you initially began
with, swap both elements (lowest element and initial index for
this iteration).
// Repeat this operation with the next element until the array is
sorted.

Code :

Please, check here the explanation for other basic sorting algorithms :

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store