Insertion Sort Algorithm on JavaScript

Question

I recently started learning algorithms based on the book Data Structures and Algorithms with JavaScript from O'Reilly.

I stopped on Chapter 12 - Sorting Algorithms.

I can not understand how Insertion Sort works.

Here is the code I am working with: pasteBin - Insertion Sort

Below is the part that is confusing to me:

function insertionSort() {
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
            this.dataStore[inner] = this.dataStore[inner-1];
            --inner;
        }
        this.dataStore[inner] = temp;
    }
    console.log(this.toString());
}

Could anyone help and comment on this code?

Answer 1

It's a sorting algorithm which starts at the beginning of the array and passes through until the end. For the item at each index, it goes back through the items at earlier indices and checks to see if it should be placed before them. If so, it swaps indices with the larger value until it settles into the index it should have.

Here's the code with some commentary, hopefully it is helpful to you.

function insertionSort() {
    /* Set up local vars */
    var temp, inner;
    /* Start at index 1, execute outer loop once per index from 1 to the last index */
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        /* Store the value at the current index */
        temp = this.dataStore[outer];
        /* Set up temporary index to decrement until we find where this value should be */
        inner = outer;
        /* As long as 'inner' is not the first index, and 
        there is an item in our array whose index is less than 
        inner, but whose value is greater than our temp value... */ 
        while (inner > 0 && (this.dataStore[inner-1] >= temp)) {
            /* Swap the value at inner with the larger value */
            this.dataStore[inner] = this.dataStore[inner-1];
            /* Decrement inner to keep moving down the array */
            --inner;
        }
        /* Finish sorting this value */
        this.dataStore[inner] = temp;
    }
    console.log(this.toString());
}

---

Here is a jsfiddle with lots of console printouts so you can step through it and see what happens at each step.

Answer 2

The main concept behind insertion sort is to sort elements by comparison.

The comparison occurs in your case for a dataStore array, containing what we assume to be comparable elements such as numbers.

In order to compare element by element, this insertion sort algorithm starts at the beginning of the dataStore array and will continue to run until the end of the array has been reached. This is accomplished by a for loop:

for (var outer = 1; outer <= this.dataStore.length - 1; ++outer)

As the algorithm goes through each element in order, it will:

1. Store the current element we are visiting in the array in a variable called temp.
2. Keep track of the location we are in the array via the inner and outer variables, where:
   • outer is our counter.
   • inner is a flag to determine whether or not we are visiting the first element in the array. Why is this important? Because there is no point in doing a comparison on the first element, on the first try.

3. It will compare the current element temp with each element that came before it in the dataStore array. This is accomplished by an inner while loop as seen here:

   while (inner > 0 && (this.dataStore[inner-1] >= temp))

This tells you that, as long as all previous visited elements in the dataStore array are greater than or equal to temp, our temporary variable used to store the current element; we want to swap these values.

Swapping them will accomplish the following:

• Assume all elements before this.dataStore[inner] are greater than 10, and the currently visited element this.dataStore[inner] equals 5. This logically means that 5 needs to be at the beginning of the array. In such case we would continue to pass 5 all the way down to this.datastore[0] thanks to the while loop. Thus making 5 the first element in the array.

At the end of this swapping, the value in temp is placed accordingly to the current position we are in the array, just to remind you which position this is, it's stored the variable outer.

TLDR: I also like Justin Powell's answer as it sticks with the code, but I thought a walk through would be more useful depending on your level of understanding. I hope it helps!

Answer 3

Starting from the inner loop check if the current element is greater than the previous if yes, exit the loop since everything is sorted for the iteration, if not swap elements because the current needs to be moved to the left because it's smaller than the previous. The inner loop makes sure to swap elements until you encounter a sorted element which results with the break exiting the loop.

After the swap occurs decrease the outer index (i) since you are going downwards to check if the upcoming element is lesser than the previous, you cannot keep the outer index (i) static.

At last, the memIndex variable serves as a reset index because at the end of your inner loop you want to move to the next index. Index (i) should always be placed at the last element of the sorted array so that the inner loop can start the comparison again.

function insertionSort(arr) {
  let memIndex = 0
  for (let i = 0; i < arr.length; i++) {
    memIndex = i;
    for (let j = i + 1; j >= 0; --j) {
      if (arr[j] >= arr[i]) {
        break;
      }
      if (arr[j] < arr[i]) {
        var temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i = i - 1;
      }
    }
    i = memIndex;
  }
  return arr;
}
const arr = [5, 1, 6, 2, 4, 9, 9, 3, 1, 1, 1];
console.log('Unsorted array', arr);
console.log('Sorted array:', insertionSort(arr));