Insertion Sort

This is an in-place comparison-based sorting algorithm.In Insertion sort the element is inserted at an appropriate 

place similar to card insertion. Here the list is divided into two parts sorted and unsorted sub-lists.In each pass, the first element of unsorted sub list is picked up and moved into the sorted sub list by inserting it in suitable position. Suppose we have ‘n’ elements, we need n-1 passes to sort the elements.

Why Insertion Sort?

Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'inserted in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.

How Insertion Sort Works?

Insertion sort works this way: It works the way you might sort a hand of playing cards:

1. We start with an empty left hand [sorted array] and the cards face down on the table [unsorted array].

2. Then remove one card [key] at a time from the table [unsorted array], and insert it into the correct position in the left hand [sorted array].

3. To find the correct position for the card, we compare it with each of the cards already in the hand, from right to left.

In Insertion sort, you compare the key element with the previous elements. If the previous elements are greater than the key element, then you move the previous element to the next position.

Start from index 1 to size of the input array.

[ 8 3 5 1 4 2 ]

Step 1 :

      key = 3 //starting from 1st index.

      Here `key` will be compared with the previous elements.

      In this case, `key` is compared with 8. since 8 > 3, move the element 8

      to the next position and insert `key` to the previous position.

      Result: [ 3 8 5 1 4 2 ]

Step 2 :

      key = 5 //2nd index

      8 > 5 //move 8 to 2nd index and insert 5 to the 1st index.

      Result: [ 3 5 8 1 4 2 ]

Step 3 :

      key = 1 //3rd index

      8 > 1     => [ 3 5 1 8 4 2 ] 

      5 > 1     => [ 3 1 5 8 4 2 ]

      3 > 1     => [ 1 3 5 8 4 2 ]

      Result: [ 1 3 5 8 4 2 ]

Step 4 :

      key = 4 //4th index

      8 > 4   => [ 1 3 5 4 8 2 ]

      5 > 4   => [ 1 3 4 5 8 2 ]

      3 > 4   ≠>  stop

      Result: [ 1 3 4 5 8 2 ]

Step 5 :

      key = 2 //5th index

      8 > 2   => [ 1 3 4 5 2 8 ]

      5 > 2   => [ 1 3 4 2 5 8 ]

      4 > 2   => [ 1 3 2 4 5 8 ]

      3 > 2   => [ 1 2 3 4 5 8 ]

      1 > 2   ≠> stop

      Result: [1 2 3 4 5 8]

INSERTION_SORT  Algorithm (A):

1. FOR j ← 2 TO length[A]

2. DO key ← A[j]

3. {Put A[j] into the sorted sequence A[1 . . j − 1]}

4. i ← j − 1

5. WHILE i > 0 and A[i] > key

6. DO A[i +1] ← A[i]

7. i ← i − 1

8. A[i + 1] ← key

   InsertionSort(arr[])

      for j = 1 to arr.length

         key = arr[j]

         i = j - 1

         while i > 0 and arr[i] > key

            arr[i+1] = arr[i]

            i = i - 1

         arr[i+1] = key

 ⇒Code For Insertion Sort in C: http://bit.ly/2Umqm3y

Characteristic of Insertion Sort:

1.    It has one of the simplest implementation

2.    It is efficient for smaller data sets, but very inefficient for larger lists.

3.    Insertion Sort is adaptive, that means it reduces its total number of steps if given a partially sorted list, hence it increases its efficiency.

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

5.    Its space complexity is less. Like Bubble Sorting, insertion sort also requires a single additional memory space.

6.    It is a Stable sorting, as it does not change the relative order of elements with equal keys

  

Complexity Analysis of Insertion Sorting

• Worst Case Time Complexity : O(n^2)
• Best Case Time Complexity : O(n)
• Average Time Complexity : O(n^2)
• Space Complexity : O(1)