Insertion Sort Using Javascript

Simple working of Insertion sort

Insertion sort works with sorting the elements while comparing the previous parsed array to put the elements in correct place. It is similar to how you sort playing cards in your hand.

Time complexity: Insertion sort has a time complexity of O(n*n).

Sudo code for insertion sort:

- we start a loop from 1 element in the array and iterate till the n-1 elements.
- we compare if the last element is greater than the current element.
- if last element is greater than current element, then we replace the current
 element with our last element and update the last elemet index by -1.
- if no more elements are greater than the current element in our previous 
parsed array then we move to the next iteration.
- at last we return the sorted array.
 

Let’s jump into the code for insertion sort:

const insertionSort = (array) => {
  for (let i = 1; i < array.length; i++) {
    let currentElement = array[i];
    let lastIndex = i - 1;

    while (lastIndex >= 0 && array[lastIndex] > currentElement) {
      array[lastIndex + 1] = array[lastIndex];
      lastIndex--;
    }
    array[lastIndex + 1] = currentElement;
  }

  return array;
};

Let’s suppose we have an array with values [4,3,2,10,12,1,5,6]. The simple working of insertion sort algorithm with be as below:

Let’s understand it line by line:

• At line 6, we have initialise a for loop that starts from 1st element and run till n-1 elements.
• At line 7, we have stored the value of current index.
• At line 8, we have stored the index of last element.
• At line 10, we have a while loop that will run until we have a sorted array for the elements till current index.
• At line 11, we are replacing the value if lastIndex+1 index(pay attention, here we are decrementing the last index every time there is a unsorted element , that is reason we are replacing lastIndex+1 value not the currentIndexValue.)
• At line 12, we are decrementing the last index so that we can check if all previous processed index are sorted or not.
• At line 14, we are replacing the lastIndex+1 element with the current element(to its right position.)
• At line 17, we are returning the sorted array.

Stay tuned for more to come, If you are new here, do checkout our Algorithms using Javascript blog, we are covering few of the most commonly used algorithms using javascript.

In the next blog, we’ll go through Heap sort.