Kyle Shevlin

Software Engineer
January 22, 2023
0 strokes bestowed

Algorithms: Insertion Sort

edit

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.

For egghead subscribers

If you enjoy learning from video content and have an egghead account, you can watch this lesson in the embed below or at https://egghead.io/lessons/javascript-sort-an-array-with-a-nested-for-loop-using-insertion-sort-in-javascript.


Finished reading?

Liked the post? Give the author a dopamine boost with a few "beard strokes". Click it up to 50 times show your appreciation.

Related Post:
Algorithms: Bubble Sort
Tags
Data Structures and Algorithms

Are you, or the company you work for, struggling with something mentioned in this article?
Would you benefit from a live training session?
Let's Talk
Kyle Shevlin's face, which is mostly a beard with eyes
Kyle Shevlin is a software engineer who specializes in JavaScript, TypeScript, React and frontend web development.

Let's talk some more about JavaScript, TypeScript, React, and software engineering.

I write a newsletter to share my thoughts and the projects I'm working on. I would love for you to join the conversation. You can unsubscribe at any time.

Data Structures and Algorithms Logo
Data Structures and Algorithms

Check out my courses!

Liked the post? You might like my courses, too. Click the button to view this course or go to Courses for more information.
I would like give thanks to those who have contributed fixes and updates to this blog. If you see something that needs some love, you can join them. This blog is open sourced at https://github.com/kyleshevlin/blog
alexloudenjacobwsmithbryndymentJacobMGEvanseclectic-codingjhsukgcreativeerikvorhesHaroenvmarktnoonandependabotmarcuslyonsbrentmclarkfederico-fiorinimedayzTowardsDeathFanchGadjonoahmateenbrandonpittmanmattridley
©2023 Kyle Shevlin. All Rights Reserved.