Selection Sort JavaScript Understanding Selection Sort in Javascript.

#algorithms #sorting #javascript #codenewbie

This is a continuation of the sorting algorithm techniques in javascript. You can find links to previous articles below:

Sorting Algorithm Articles
Bubble Sort

Alright, let's get in straight to selection sort.

The prerequisites to better understand this sorting algorithm, you are required to have a better understanding of BIG O NOTATION and Bubble sort, so if it's your first time to hear them. I got you covered, just follow the link above in the table.

What is selection sort and how does it work?

Selection sort as the name implies is also a comparison sorting algorithm, where it has to walk or loop through a given datastructure and compare each number for the sake of computing a minimum number, so that in the end it can swap it with the number found at the beginning of the array.

Selection Sort is similar to bubble sort, the only slight difference is that instead of placing the sorted items in the end of the array as bubble sort does. It places them in the beginning, And the value placed in the beginning is always the smallest among others.

Let's first review the Selection Sort Pseudo Code

store the first element index as the smallest value, you've seen so far.
walk through the array and try to find another smallest value compared to the initial one.
if the smaller number is found, designate that number index to be the new minimum. note that we are working with indices here which basically helps us in swapping numbers.
if the current minimum is not equal to what we initially began with, swap the 2 values.
And repeat this process with the next element until the whole array is sorted. the reason why we select the next element is to avoid the redudancy of going through the already sorted elements.

// a swap helper function.
const swap = (arr, i, j) => [arr[i], arr[j]] = [arr[j], arr[i]];

const selectionSort = (arr) => {
  // start looping at the beginning of the array.
  for(let i = 0; i < arr.length; i++) {
    // select the element's index at the beginning as the current minimum number.
    let min = i;
    // loop thourgh the array from the next element of the array
   // this will help us in checking only against the unsorted
   // elements, as we know the elements before it are already sorted.
    for(let j = i + 1; j < arr.length; j++){
      // check if the current element is less than the initial minimum
     // and assign the minimum to be the current element if that's the case.
      if(arr[j] < arr[min]) min = j;
    }
    // at this stage, we are checking if the new minimum index number
   // is not equal to the one we begin with.
   // analyse the code, and you will notice that we are still in the outer loop where i is still 0.
   // which was our initial minimum number value, so after
   // looping through the array again with the inner loop and 
  // we found another new minimun number, we are now swapping those 2 values.
 // after that, we repeat the same process until the array is sorted.
    i !== min && swap(arr, i, min);
  }
  return arr;
};

so that's the implementation of selection sort but we also need to look into its BIG O NOTATION.

for the worst case scenarios, let's say we have an array with 1M elements, the selection sort will have to loop 2M times for it to sort the array and that is not efficient at all. so it is Quadratic O(n^2)

the same analogy applies even on best and average case where it is O(n^2), just because of its behaviours of looping everytime from the beginning with any optimazition.

its time complexity makes it the worse one compared to others because it takes forever to sort even a nearly sorted array.

based on the fact, that we are only initiating 3 variables (min, i, j). This makes its space complexity constant O(1), there are no other variables required other than that.