Understanding Insertion Sort in Javascript.

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

Sorting Algorithm Articles
Bubble Sort
Selection Sort

A quick definition of insertion sort is that it builds up the sort by gradually creating a larger left fraction of the array which is always sorted.

Let's say we have [5,3,2,6,8] as our initial array, insertion sort will assume 5 is already sorted, and then selects the next element which is 3 and compare it to 5, and if 3 is less than 5, then that means 3 should be inserted right before 5, but when the next element is greater than 5, then that element will remain in its position. So that's how the sorted array gradually grows little by little.

Let's take a look at insertion sort pseudo code.

• we start by picking the second element of the array.
• we compare it to the element before it, and swap if that element is less than the one before it.
• then continue to the next element, and iterate through the left portion, which is sorted by the way and try to insert that current element in its correct place in the sorted portion.
• repeat this process until the array is sorted, and make sure you return the sorted array.

Alright, It's time to get our hands dirty now.

const insertionSort = (arr) => {

  // as the pseudocode implies, we need to start looping from
  // the second element by assuming the first element is in
 // left portion of the array which is always sorted.

  for(let i = 1; i < arr.length; i++){

    // we also need to select our actual current element,
   // this will aid us to compare it to the values of our
  // sorted portion and also finding its correct spot.

    let currentEl = arr[i];

  // the next loop will help us go through the sorted portion
  // of the array, and notice that it always goes behind i.
  // and it keeps going as long as it is still greater or equal to 0,
  // with that said, it loops until it hits the end of the
  // portion of the array, which is the beginning of the actual
  // array in this context.

  // Eg: imagine a scenario where i = 10, then j will be 9,
  // and j has also to walk backwards, which will help it to
  // compare the currentEl to the values in the sorted portion.
 // so that is the reason why it decrements instead of incrementing.

  // but when the currentEl of i is less than the one of j, that
 // when it is like this 536 >  89. then that mean we have found 
 // a new value to insert in our sorted portion.
 // that is what that condition arr[j] > currentEl means in that
// loop. note that the condition can also be written inside the
// inner loop scope.

    for(var j = i - 1; j >= 0 && arr[j] > currentEl; j--){

       // so here is where the exchange of numbers begins,
       // when it has been found that the arr[j] > currentEl,
       // then in the sorted array, we exchange the current value of
       // arr[j + 1] to be the value of arr[j] and decrement j.      
       // we will repeat this process till arr[j] < currentEl or 
       // when the loop end; 

       arr[j+1] = arr[j]; 
    }

    // from the operation above, j has moved down because it is no longer greater than the currentEl, and that is the magic moment for us.
   // cause now we know where our currentEl from i belongs, 
  // and that is just in front of the current j, which is j + 1. note also that we are doing this operation in the outer loop scope, 
  // and j is available because we made it global while initiating it.

    arr[j+1] = currentEl;
  }

  // and finally, we return our sorted array.
  return arr;
}

insertionSort([345,56,96,2,39,70.-0.65,-0,13,65,-54,134,536,89,223,6890,5,12134]);

let's walk through it again in a different way to concretely understand it.

  // suppose we have this array below, and it needs to be sorted.
   arr = [546,2,876,-1,6];
   // firststep, i = 1, currentEl = arr[i] which is equal to 2.
   // j = 0, and we compare arr[j] > currentEL. i.e: is 546 greater
  // than 2, and that is true.
  // we move 546 ahead by replacing a value which was on arr[j + 1] with the value of arr[j].
// and now our array looks like this inside the inner loop
arr = [546,546,876,-1,-6]
// and remember we have saved our currentEl which is 2.
// after that j decrements to -1, and that means its loop finishes
// because j is no longer greater or equal to 0. it is now -1 which
// is less than 0.
// in the loop scope of i. i.e: the outer loop, we need to exchange our numbers.
// and our array is like this.
        0   1   2   3  4
arr = [546,546,876,-1,-6]
// j is now -1 and the correct spot of our currentEl which is 2,
// is on 0 index, so that is why we say that arr[j + 1]. i.e: arr[-1 + 1]
// which results in arr[0] should equal to our currentEl value.
// so now our array looks like this
arr = [2, 546, 876, -1, -6]
// after this operation, as we are in the outer loop, i will be // incremented to 2, so now let's look at the second step.

// our current arr looks like this 
arr = [2, 546, 876, -1, -6]
// second step: i = 2, currentEl = 876.
// j = 1. arr[j] = 546.
// compare is 546 > 876? the answer is no.
// decrement j to 0, and check if 2 > 876. the answer is NOO.
// decrement j to -1, and boom we're out of j loop.
// our current arr is still like this
arr = [2, 546, 876, -1, -6] // as there's nothing to sort at the moment
// loop of i again, and let's now increment i to 1.
// now i = 3, currentEl = -1.
// j = 3 - 1 (2), arr[2] = 876.
// is 876 > -1, YES, and exchange values.
arr = [2, 546, 876, 876, -6]
// decrement j to 1 and check if 546 > -1, and that is true.
arr = [2, 546, 546, 876, -6]
// decrement j to 0, and check if 2 > -1, TRUE. 
arr = [2, 2, 546, 876, -6]
// decrement j to -1, and we are out of its loop scope now.
// perform the operation arr[j+1] = currentEl.
// which means arr[-1+1] = -1, j = 0, currentEl is -1.
arr = [-1,2,546,876,-6]
// after that we increment i to 1, and its value is now 4
// currentEl is arr[4]. the value is -6.
// j = 4 - 1, arr[j] = 876.
// check if 876 > -6. TRUE, moves 876 to j + 1
arr = [-1,2,546,876,876]
// decrement j to 2 and check if 546 > -6. TRUE
arr = [-1,2,546,546,876]
// decrement j to 1 and check if 2 > -6. TRUE
arr = [-1,2,2,546,876]
// decrement j to 0 and check if -1 > -6. TRUE
arr = [-1,-1,2,546,876]
// decrement j to -1 and we're out of its loop.
// perform the operation of exchanging arr[j+1] = currentEL
arr = [-6,-1,2,546,876] // and we increment i to 5 and i is no longer 
// less than the length of the array which 5. is 5 < 5. NO
// this will get us out of the outer loop of i. and then
// we return our current array which looks like follow
arr = [-6,-1,2,546,876] // and BOOM, we are sorted now.

last but not least, let's talk a little bit about the BIG O NOTATION of insertion sort.

worstcase scenarios: it is quadratic O(n^2)
averagecase scenarios: it is also quadratic.
bestcase scenarios: it is linear O(n).

below is a quick picture of the BIG O notation of all the sorting algorithm we looked at so far.

And that's it. and thanks for reading this far.
Keep Learning, Keep Growing.
hasta la proxima vez