Insertion Sort JavaScript Insertion Sorting for Beginners in JS

Earlier this week I wrote a post outlining a basic bubble sorting algorithm. Today I am going to tackle the insertion sort algorithm. The motivation behind these posts being that I understand what they are but need to tighten up my actual understanding of them, considering I'm a professional dev who uses JS all day every day.

What is Insertion Sort?

Insertion sort is a method of sorting an array by dividing the array into a 'sorted' portion and 'unsorted' portion. Then we compare the unsorted item to see if it is larger than the previous element, if not we insert the new item. Basically we are looking from left to right and sorting as we go.

Let's start building our insertionSort function.

Step 1

const insertionSort = arr => {
  const len = arr.length;
  return arr;
};

I have always found it better to save the array length in a variable instead of continually referencing arr.length.

Step 2

const insertionSort = arr => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    //
  }
  return arr;
};

Now we have a for loop looping over each element of the array, and we will do our sorting inside of it.

Step 3

const insertionSort = arr => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let el = arr[i];
    let j;
  }
  return arr;
};

Set up a variable el to hold the current value and initialize another variable j and set it outside of our next for loop to maintain appropriate scoping.

Step 4

const insertionSort = arr => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let el = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > el; j--) {
      arr[j + 1] = arr[j];
    }
  }
  return arr;
};

Now we set up a for loop inside our first for loop. We assign j the value of our current array position minus 1 and evaluate it against if it is greater than 0 and if the current element is smaller than the starting loop element.

Step 5

const insertionSort = arr => {
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    let el = arr[i];
    let j;

    for (j = i - 1; j >= 0 && arr[j] > el; j--) {
      arr[j + 1] = arr[j];
    }
    arr[j + 1] = el;
  }
  return arr;
};

Finally we add assign the value el to the current index position in the array. Using j+1 because we are initially setting the value of j to i-1.

There is the basics of an insertion sort algorithm!