Insertion Sort

Insertion Sorting 

It is a simple sorting algorithm which sorts the array by shifting elements one by one. Following are the important characteristics of insertion sort.

1. It has one of the simplest implementation.

2. Efficient for small data sets, but very inefficient for large data sets.

3. This is Adaptive, i.e, it reduces its total number of steps if given a particular sorted data.

4. It is better than Selection Sort and Bubble Sort algorithms.

5.  It is Stable, i.e., does not change the relative order of elements with equal keys.

  

As we can see here, in insertion sort, we pick up key, and compares it with elements ahead of it, and plus the key in the right place.

6 has nothing before it.

5 is compared to 6 and is inserted before 6.

3 is smaller than 5 and 6, so its inserted before 5.

And this goes on.....

Sorting using Insertion Sort Algoithm

function insertionsort(input) {

    var activeNumber;

    for (var i = 1; i < input.length; i++) {

        activeNumber = input[i];

        for (var j = i - 1; j >= 0; j--) {

            if (input[j] > activeNumber) {

                input[j + 1] = input[j];

            } else {

                break;

            }

        }

        input[j + 1] = activeNumber

    }

}

var myinput = [24, 10, 17, 9, 5, 9, 1, 23, 300];

insertionSort(myinput);

Now lets, understand the above simple insertion sort algorithm. We took an array with 9 intergers.

We took a variable activeNumber, in which we put each element of the array, in each pass, starting 

from the second element, that is input[1].

Then using the for loop, we iterate, until j becomes equal to zero . Inside the for loop  we have if condition that will find an element which is greater than activeNumber, and then we insert the activeNumber at that position.

In the above array, first we pick 10 as activeNumber, we compare it with 24(element before 10), 10 is smaller than 24, we shift 10 before 24. Then we pick 17, and compare it with 24 and 10, 17 is smaller than 24, we shift 17 before 24. And this goes on, until complete array gets sorted.

Example: Insertion Sort