© 2019 - First Crazy Developer (Abhishek Kumar)

### Insertion Sort - Sorting Algorithms

Insertion Sort

In application development there are lot of scenario comes when we need to sorting our listed or arrays data. Provided list or array can be n number size. So when we write a code to sorting that data, we should consider the most efficient way to do that, because that process impact on your application performance base on time & space complexity. So for that you'll need a sorting algorithm. To understand the more complex and efficient sorting algorithms, it's important to first understand the simpler, but slower algorithms.

In previous post in data structure we discussed about Bubble Sort and today we will discuss about Insertion Sort. After Bubble Sort, It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Insertion Sort is a simple sorting algorithm that works the way we sort playing cards in our hands.

But in our card example, the new card could be smaller than some of the cards you're already holding, and so you go down the line, comparing the new card against each card in your hand, until you find the place to put it. You insert the new card in the right place, and once again, your hand holds fully sorted cards. Then the dealer gives you another card, and you repeat the same procedure. Then another card, and another card, and so on, until the dealer stops giving you cards.

This is the idea behind Insertion Sort. Loop over positions in the array, starting with index 1. Each new position is like the new card handed to you by the dealer, and you need to insert it into the correct place in the sorted subarray to the left of that position.

Example: With the given array is: [7, 1, 6 ,2, 4 ,3]

First Pass:

[7,1,6,2,4,3] –>  Here algorithm start compare between key value(7) to 0 index value(1) and swap since (7>1)  >>  [1,7,6,2,4,3]

After this iteration first pass is completed with updated  [1,7,6,2,4,3]

Important Note: In Insertion Sorting  inner loop iterate start from  n number times with condition key value is less than current index value of inner loop and inner loop values is greater than equal to 0. Here n number is outer loop values.

Second Pass:

[1 7 6 2 4 3] –> Here algorithm start compare between key value(6) to 1 index value (7>6) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,7,7,2,4,3]

[1,7,7,2,4,3] –> now compare  between key value(6) to 0 index value(1>6) -- condition false- inner loop terminate - now replace key value with current inner loop index value-- updated array >> [1,6,7,2,4,3]

After this second iteration this pass is completed with updated array- [1,6,7,2,4,3]

Third Pass:

[1,6,7,2,4,3] -> Here algorithm start compare between key value(2) to 2 index  value (7>2) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,6,7,7,4,3]

[1,6,7,2,4,3] -> now compare between key value(2) to 1 index value (6>2) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,6,6,7,4,3]

[1,7,7,2,4,3] –> now compare  between key value(2) to 0 index value (1>2) -- condition false -- inner loop terminate - now replace key value with current inner loop index value-- updated array [1,2,6,7,4,3]

After this third iteration this pass is completed with updated array- [1,2,6,7,4,3]

Fourth Pass:

[1,2,6,7,4,3] -> Here algorithm start compare between key value(4) to 3 index value (7>4) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,2,6,7,7,3]

[1,2,6,7,7,3] -> now compare between key value(4) to 2 index value (6>4) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,2,6,6,7,3]

[1,2,6,6,7,3] –> now compare  between key value(4) to 1 index value (2>4) -- condition false -- inner loop terminate - now replace key value with current inner loop index value-- updated array >>  [1,2,4,6,7,3]

After this fourth iteration this pass is completed with updated array- [1,2,4,6,7,3]

Fifth Pass:

[1,2,4,6,7,3] -> Here algorithm start compare between key value(3) to [4 index] value (7>3) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,2,4,6,7,7]

[1,2,4,6,7,7] -> now compare between key value(3) to [3 index] value (6>3) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,2,4,6,6,7]

[1,2,4,6,6,7] –> now compare  between key value(3) to [2 index] value (4>3) - condition true -- switch value left to right with current inner loop index value-- now update array >> [1,2,4,4,6,7]

[1,2,4,4,6,7] –> now compare  between key value(3) to [1 index] value (2>3) -- condition false -- inner loop terminate - now replace key value with current inner loop index value-- updated array >> [1,2,3,4,6,7]

After this fourth iteration  this pass is completed with updated array- [1,2,3,4,6,7] Now the array is sorted. If we discussed the above scenario what we found?

Look the following code:

` 1: int unSortedArray = [7, 1, 6 ,2, 4 ,3];`
` 2:  `
` 3: int outerLoop, innerLoop, keyValues;`
` 4:  `
``` 5: for(outerLoop=1; i
6:
7: {
8:
9:   key = unSortedArray[outerLoop];
10:
11:   innerLoop = outerLoop-1;
12:
13:   while(innerLoop>=0 && key < a[innerLoop])
14:
15:   {
16:
17:     unSortedArray[innerLoop+1] = unSortedArray[innerLoop];
18:
19:     innerLoop--;
20:
21:   }
22:
23:   unSortedArray[innerLoop+1] = keyValues;
24:
25: }
```

In above code is the algorithm, to sort array with Insertion Sort. When we go through the above code, If we compare with Bubble Sort which sort data from right to left but in Insertion Sort we sort data from left to right. In Bubble Sort we compare between pair but in this sorting we compare in linear way and switch the values.

One note about shifting versus exchanging is also important. In general, a shift operation requires approximately a third of the processing work of an exchange since only one assignment is performed. In benchmark studies, insertion sort will show very good performance.

Final algorithm:

` 1: for i = 1 to length(A) - 1`
` 2:  `
` 3:     x = A[i]`
` 4:  `
` 5:     j = i`
` 6:  `
` 7:     while j > 0 and A[j-1] > x`
` 8:  `
` 9:         A[j] = A[j-1]`
` 10:  `
` 11:         j = j - 1`
` 12:  `
` 13:     end while`
` 14:  `
` 15:     A[j] = x`
` 16:  `
` 17:  end for`

Final Output of Bubble Sorting:

• Stable: Yes
• Auxiliary Space: O(1) extra space
• Time Complexity: O(n*n) comparisons and swaps
• Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.
• Algorithmic Paradigm: Incremental Approach

## Best, worst, and average cases

The best case input is an array that is already sorted. In this case insertion sort has a linear running time (i.e., O(n)). During each iteration, the first remainingelement of the input is only compared with the right-most element of the sorted subsection of the array.

The simplest worst case input is an array sorted in reverse order. The set of all worst case inputs consists of all arrays where each element is the smallest or second-smallest of the elements before it. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array beforeinserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2)).

The average case is also quadratic, which makes insertion sort impractical for sorting large arrays. However, insertion sort is one of the fastest algorithms for sorting very small arrays, even faster than quicksort; indeed, good quicksort implementations use insertion sort for arrays smaller than a certain threshold, also when arising as subproblems; the exact threshold must be determined experimentally and depends on the machine, but is commonly around ten. Home Page 30 June 2015