DEV Community

Cover image for Insertion Sorting for Beginners in JS
Ryan Dunton
Ryan Dunton

Posted on

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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;
};
Enter fullscreen mode Exit fullscreen mode

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!

Top comments (2)

Collapse
 
yunielrc profile image
Yuniel
const insertionSort = (array) => {
  const arr = Array.from(array); // avoid side effects
  for (let i = 1; i < arr.length; i++) {
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
    }
  }
  return arr;
};
Enter fullscreen mode Exit fullscreen mode
Collapse
 
edemagbenyo profile image
Edem Agbenyo

Nice implementation of the insertion sort!