Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Insertion Sort Algorithm on JavaScript

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?

like image 516
Mikhail Avatar asked Nov 04 '15 19:11

Mikhail


People also ask

How do you use insertion sort in JavaScript?

Insertion Sort AlgorithmIterate from arr[1] to arr[N] over the array. Compare the current element (key) to its predecessor. If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Which sorting algorithm is used in JavaScript?

JavaScript by default uses insertion sort for the sort() method. This means that it is not appropriate when sorting large data sets. When dealing with large data sets, one should consider other sorting algorithms such as merge sort.

How insertion sort works with example?

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration. Insertion sort works similarly as we sort cards in our hand in a card game. We assume that the first card is already sorted then, we select an unsorted card.

What is insertion sort algorithm in data structure?

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort.


3 Answers

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.

like image 111
JstnPwll Avatar answered Oct 15 '22 08:10

JstnPwll


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!

like image 33
AGE Avatar answered Oct 15 '22 06:10

AGE


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));
like image 31
Eugen Sunic Avatar answered Oct 15 '22 07:10

Eugen Sunic