Insertion Sort

In case you were wondering

Photo by Yaoqi LAI on Unsplash

This week I’m having a look at Insertion sort, another simple method to sort an array. In short, Insertion sort takes one value at the time, and checks it only compared to items to its left. If the item is smaller, it will be swap them until all the numbers to its left are smaller. This means that for each item, all the items to its left will already be sorted.

https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif

In practice at each iteration we are dividing the input in two separate arrays. The left array will always be sorted (a number on it’s own it’s sorted) and the right array is waiting to be sorted. We take the item with index = 0, which goes in the sorted array and nothing else needs to be done. Then we take the item with index = 1, which is were we actually start checking who’s bigger/smaller. The item that we compare with the left side of the array is called the key. The key gets compared to all items of the sorted array starting from the last, until the key is also sorted. Then we move to the next index of the initial array and the whole input is sorted. So each key is inserted in the sorted array, hence the name Insertion sort.

https://tamalweb.com/notes-on-algorithms-3-insertion-sort

In pseudo-code:

array = [several items]
for (i = 1 to array.length) {
   key = array[i]
   j = i - 1
   while (array[j] > key & j > 0){   // if array[j] is bigger
      array[j+1] = array[j]          // we move it up one space
      j = j - 1
   }
   array[j+1] = key      // we place our key in its sorted spot
}

Example:

Let’s look at the array = [4,2,5,3,1].

We start sorting from index = 1 cause we for each item we need to be able to compare it to the item to its left.

Let’s take that element (2) and compare to the array made of the items to its left, which in this case is only made of one number (4). 2 < 4 so the items are swapped. Now our array = [2,4,5,3,1]. Let’s go through the rest of the array repeating the process until it’s completely sorted.

Iteration 1: comparing the element at index = 1(2) with 4: [4,2,5,3,1] → [2,4,5,3,1]

Iteration 2: comparing the element at index = 2(5) with 4: [2,4,5,3,1] → [2,4,5,3,1]

Iteration 3: comparing the element at index = 3(3) with 5 and 4: [2,4,5,3,1] → [2,4,3,5,1] → [2,3,4,5,1]

Iteration 4: comparing the element at index = 4(1) with 5, 4, 3 and 2: [2,3,4,5,1] → [2,3,4,1,5] → [2,3,1,4,5] → [2,1,3,4,5] → [1,2,3,4,5]

Notice how after each step, all the items to the left of the item that we are comparing are already sorted.

In actual code:

let insertionSort = (array) => {
   for (i = 1; i < array.length; i++) {
      let key = array[i];
      let j = i - 1;
      while (j >= 0 && array[j] > key) {
         array[j + 1] = array[j]
         j = j - 1;
      }
      array[j + 1] = key;
   }
   return array;
}

Just before the end we assign the value of the key to input[j + 1] because array[j] corresponds to the first item in the sorted array whose value is less than the key’s value, so the key goes to the right of that.

Ta-dah!

They just understood Insertion Sort

That’s it, thanks for reading! Don’t forget to watch Insertion sort if it was Folk dance.