Sorting Algorithms : Selection Sort

(Javascript implementation)

Selection Sort Algorithm

Time Complexity :

How it works :

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 :

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 :

Computer Science and Software Engineering