18 Dec 2017

Insertion Sort

Insertion sort is an algorithm used to sort an unordered array of items.

Given an unsorted array arr, insertion sort builds up an array of sorted elements “in-place”.

Visualize sorting an unsorted deck of cards. Take off the first card and put it into a sorted pile. Then take the next card key off the deck.

Compare key with each card in the sorted pile from greatest to least, until you find the card which key is greater than. Insert key there. Continue until deck is empty.

Or, in array-speak, for each element key in the original array, excluding the first and the last, we:

Test key against all preceding elements from indices (i...0]

is key smaller than the element?
- shift arr[j] forward by one to j+1
  - this duplicates j in the array. the duplicate will be overwritten in the next loop, either with the adjacent smaller element or, if we find the position for key, with key itself
  - decrease j by one
is key larger than arr[j] (or are we at the beginning of the array, j===0)?
- we have found the position for key! insert key at j+1

The code looks like this:

function insertionSort(arr) {
  for (var i = 1; i < arr.length; i++) {
    let key = arr[i];
    console.log(i, key);
    j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

What the…?

It’s tough to visualize. Let’s take it step by step in sorting var arr = [3,2,1] with length 3.

i is 1, key is `arr[i] => 2`

j===0. arr[0]===3.

3>2 && j>=0 is true, so we execute the while loop body.
arr[0+1]=arr[0]
j--

The array now looks like this: [3,3,1]

j===-1. arr[0]===4.

-1>=0 is false. We do not execute the while loop body.
Instead, we replace arr[j+1] (arr[0]) with key.

The array now looks like this: [2,3,1]

i is 2, key is `arr[2] => 1`

j===1. arr[1]===3.

3>1&&j>=0 is true, so we execute the while loop body.
arr[1+1]=arr[1]
j--

The array now looks like this: [2,3,3]

j===0. arr[0]===2.

2>1 && j>=0 is true, so we execute the while loop body.
arr[1+1]=arr[1]
j--

The array now looks like this: [2,2,3]

j===-1. arr[0]===4.

-1>=0 is false. We do not execute the while loop body.
Instead, we replace arr[j+1] (arr[0]) with key.

The array now looks like this: [1,2,3]

i is 3. `3<3` is false

We exit the for loop and return the sorted array, [1,2,3].

Insertion Sort

What the…?

i is 1, key is arr[i] => 2

i is 2, key is arr[2] => 1

i is 3. 3<3 is false

i is 1, key is `arr[i] => 2`

i is 2, key is `arr[2] => 1`

i is 3. `3<3` is false