Notes on Algorithms 3, Insertion Sort

Insertion Sort is yet another way to sort a list in ascending order just like we did with Selection Sort last week. Similar to selection sort, it will keep comparing the current value with other items and place it when it finds a suitable position.

Given an array of unsorted integers, it will divide the list in 2 sections. The sorted left array and the unsorted right array. It will take the 1th item of the array as the key (or the right index) to make the comparisons.

Since we start with the only one item in the left, we can say this array is sorted because an array with only one item is always a sorted array. The idea is, we will keep the left array sorted all the time.

Take the 1th item (the key) and compare it with the items in the sorted section. If the item is greater than the key, move this item one position to the right.

At the end of the run I will have to drop this key into the new vacant position.

Keep repeating this process for all the other items to find a sorted array.

JavaScript Implementation:

Start with a function which will take an array. It will start with the 1th item to be the right index (key). We will use a for loop to iterate over the array.

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    // To be coded..
  }
  return array;
}

We will create another loop inside the first loop. To keep things simple, I will create a new function insert() with the loop inside. It will take the array and the rightIndex:

function insert(array, rightIndex) {
  let keyValue = array[rightIndex];
  let index = rightIndex;
  for (let i = rightIndex - 1; i >= 0 && array[i] > keyValue; i--) {
    index = i;
    array[i + 1] = array[i];
  }
  array[index] = keyValue;
}

Breaking down the code:

The function takes the array and the rightIndex (the current index) to make the comparisons.

Inside I have a for loop. I start with i as the rightIndex – 1. This is because I will compare the rightIndex item with the item to its left. If I compare rightIndex with rightIndex, I will not see any progress. The array will loop over from right to left, which means starting with large number and keep going down till 0. So the condition is i should be more than or equal to 0.

If I find an array item which is greater than the keyValue, I will move that item to the right: array[i + 1] = array[ i ]

By doing this I will keep moving the items to the right of the sorted array. At the end of the loop I will place the value into the correct position.

Finding the correct position to drop the key value:

I save the rightIndex in index variable. Index variable will be the position where to drop this current key at the end of the insert operation. Let’s say the key value is 5 (the rightIndex is 4) and the sorted left array is [1, 2, 3, 4].

Set i to rightIndex – 1 = 3.

Does array[3] (4) is greater than key value 5? No.

In this case, the loop will run and see none of the items in this array are greater than the key value 5.

So it will not run anything inside the loop, get out of the loop and set the value to array[index] (which was set to rightIndex).

In another case the key value is 2 and the sorted left array is [1, 3, 4, 5]

It meets the condition of 5 being greater than 2. So we move 5 to the right.

Now the array looks like: [1, 3, 4, 5, 5]

Do the same with 4 to find the array to be: [1, 3, 4, 4, 5]

In the next run: [1, 3, 3, 4, 5]

In the next run 1 is no longer greater than 2 so I will need to stop. But I will need to know the position where to drop this 2. So each time of the loop I will update index with the current running index. The last running index was 1 so I put 2 in the position 1 to get the final array of [1, 2, 3, 4, 5]

Putting it all together:

function insert(array, rightIndex) {
  let keyValue = array[rightIndex];
  let index = rightIndex;
  for (let i = rightIndex - 1; i >= 0 && array[i] > keyValue; i--) {
    index = i;
    array[i + 1] = array[i];
  }
  array[index] = keyValue;
}

function insertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    insert(array, i);
  }
  return array;
}

So far this is the correct implementation I know about insertion sort. It’s a bit hard to grasp, but I’m sure over time I will fully understand it.

The algorithm takes O(n^2) times to complete. Find a heavily commented version of the code and tests in github.


Leave a Reply

Your email address will not be published. Required fields are marked *