Insertion Sort Discrepancy

[jamestrenda]

TLDR;

Change the word swap to shift.

=============================

As someone who is new to these algorithms, I found your description of Insertion Sort a bit confusing, especially after seeing your solution.

With insertion sort, you treat the first part of your list as sorted and the second part of your list as unsorted. Our algorithm will start by saying everything [before] the 1 index (so just index 0, the first element) is sorted and everything after unsorted. By definition a list of one is already sorted.

So far so good...

From there, we start with the next element in the list (in this case, the 1 index, the second element) and loop backwards over our sorted list, asking "is the element that I'm looking to insert larger than what's here? If not, you work your way to the back of the array. If you land at the first element of the sorted part of the list, what you have is smaller than everything else and you put it at the start. You then repeat this until you've done it over the whole list!

Ok...here's where it gets confusing...(emphasis mine)...

The mechanism by which we'll do this is that we'll keep moving bigger elements to the right by swapping items in the array as we move across the element. When we come to the place where we're going to insert, we'll stop doing those swaps

Based on that description, having done no other research on the algorithm, here is my solution that keeps swapping items inside the inner for loop until it is in the right position.

function insertionSort(nums) {
  for (let i = 1; i < nums.length; i++) {
    for (let j = i; j > 0; j--) {
      if (nums[j] < nums[j - 1]) {
        const temp = nums[j];
        nums[j] = nums[j - 1];
        nums[j - 1] = temp;
      }
    }
  }
  return nums;
}

This passes the test and the Sort Visualizer nicely demonstrates how each out-of-order item works its way backwards, swapping one index at a time, until it's in the right position.

Your solution, which, after doing some research, I've learned is the correct implementation of Insertion Sort, is about 2x faster than the solution I came up with. Yet, I feel like my solution is more aligned with the way you described Insertion Sort (with swaps) on the course website.

Apparently, with Insertion Sort, you're not really swapping items. Instead, you store the out-of-order item in a variable like numberToInsert and then you start shifting items to the right until you find the correct position for numberToInsert. Then, once you find the correct position, and only then, you insert it at its correct position. In other words, there is no swapping at all.