Algorithms: Insertion Sort

January 22, 2023

0 strokes bestowed

Algorithms: Insertion Sort

Let me start this post with a question. Is an array of a single item a sorted array?

Not a trick question! It is, and we use this fact with insertion sort.

In the previous post on bubble sort, our algorithm spent a lot of time comparing items that were already sorted, especially near the end of the sort. That's really inefficient. How might we be able to avoid making these unnecessary comparisons?

If we were able to track an array that we knew to be sorted, we could stop looping past this array and instead insert items, one by one, into their correct position. Doing so, would save us a few unnecessary comparisons.

To accomplish this, we treat the first item in the array as a sorted list of a single item. Then, we compare the rest of the items to the items in this sorted list. When we find a spot for our item, we insert it into the sorted portion. By the time we finish looping through each item, our list will be sorted. No need for a final loop to verify nothing changed.

The details

The insertion sort algorithm goes like this:

Treat the first item as a sorted
Thus, starting from the 2nd item in the array, loop through each item
For each item:
- Loop through the sorted portion of our array
- Compare each item in the sorted portion to the item in the outer loop
- If the outer item is less than the inner item
  - Remove the outer item from its current position
  - Splice it into the inner position

function insertionSort(items) {
  let i
  let j

  /**
   * Loop from the start of the unsorted portion of our array
   * aka the second item
   */
  for (i = 1; i < items.length; i++) {
    /**
     * Loop thru the sorted portion of our array
     * aka from the first item to our outer item
     */
    for (j = 0; j < i; j++) {
      /**
       * Compare the item at `i` with `j`
       */
      if (items[i] < items[j]) {
        /**
         * We can remove the item at `i` out and destructure it
         */
        const [item] = items.splice(i, 1)

        /**
         * And splice the item back in at `j`
         */
        items.splice(j, 0, item)
      }
    }
  }

  return items
}

We can see it in action here:

Comparisons: 0

Take notice that while we still do a lot of comparisons, we do quite a bit fewer than we did with bubble sort. In running the component above a few times in testing, I noticed it was about 1/2 as many as the bubble sort on average. That's a pretty good improvement. But we can still do better, and we'll learn how soon.