**WHAT IS INSERTION SORT :**

Insertion sort is a sorting algorithm which sorts the input data by putting elements into the sorted array one at a time .

It compares the next element in the array and puts it in the right place .

WHY INSERTION SORT :

When there are couple of sorting algorithms available why should i hit insertion sort ???

When the number of elements to be sorted is much lower , insertion sort gives us a very good result compared to others. Hence use it when the data set is low.

**HOW INSERTION SORT WORKS :**

Lets take an input tape with 5 elements in descending order.

5 **4** 3 2 1

4 5 **3** 2 1

3 4 5 **2** 1

2 3 4 5 **1
**

1 2 3 4 5

On each iteration , it takes one element at a time and compares with the next element and places it in the right position.

First Iteration we take 4 as Key element . compare it with 5 . Since 4 is lesser we swap 4 and 5.

Second Iteration we take 3 as Key element . compare it with 5. 3 is lesser than 5 . Swap it . Yes, 3 is lesser than 4 also . Hence continue the swap until you place the element in the right place.

**CODE FOR INSERTION SORT :**

#include <iostream> using namespace std; void swap(int &a, int &b); int main() { // initializing the variables int a[10000]; int c = 0; int n; // insert elements in descending order cin >> n; for(int i=n ; i>0; i--) { a[c] = i; c++; } // print the array before sorting cout << "Array Before Sorting" << endl; for(int i=0 ; i<n; i++) cout << a[i] << endl; // insertion sort logic starts here for(int i=0 ; i<n-1; i++) { int key = a[i+1]; int pos = i+1; for(int j=i; j>=0 ;j--) { if(a[pos] < a[j]) { swap(a[pos],a[j]); pos--; } } } // insertion sort logic ends here. Printing the array after sort. cout << "Array AfterSorting" << endl; for(int i=0 ; i<n; i++) cout << a[i] << endl; return 0; } void swap(int &a, int &b) { int t; t = a; a = b; b = t; }

**EXPLANATION :**

**for(int i=0 ; i<n-1; i++)**

Each time we need to pick an element and put it in the right place. Hence we need a loop that runs through an array.

**int key = a[i+1];**

** int pos = i+1;**

On each iteration we choose one element as key and place it in the right place.

Hence , we are choosing the element which is in i+1 place as key and noting down its position in variable pos.

**for(int j=i; j>=0 ;j–)**

This innner for loop helps to compare the previous elements . we need to check till the first element and place the key element at the right place.

**if(a[pos] < a[j])**

** {**

** swap(a[pos],a[j]);**

** pos–;**

** }**

This condition checks with the previous element . If it is greater then it swaps the element .

**TRIAL**

Lets run this program for 5 elements .

Now input tape contains 5 4 3 2 1

First Iteration :

i=0 , key = 4, pos = 1

j=0 , 0>=0 is true hence

if(4<5) swap(4,5); pos– => pos = 0

Now, input tape contains : 4 5 3 2 1

Second Iteration:

i=1, 1<5, key = 3 and pos = 2 j=1, 1>=0

if(3<5) – true swap(3,5); Now input tape contains 4 3 5 2 1 pos — => pos =1

j– => j=0

j=0; 0>=0

if(3 < 4) – true swap(3,4) pos– = > pos = 0

Now input tape contains 3 4 5 2 1

Simillary loop goes on sorting .

BEST , WORST AND AVERAGE CASES

The program given above is for worst case . since the elements are in descending order . In this case, we need to compare all the elements with 2 for loops . The time complexity will be quadratic

For Best case scenario put the elements in the sorted order.

for(int i=0 ; i<5; i++) a[i] = i+1;

Eventhough the elements are in the sorted order, the outer for loop will be running for n comparisons. Hence the best case is O(N);

AVERAGE CASE :

Generate random numbers and insert it into array .

#include <stdlib.h> srand(time(NULL)); for(int i=0 ; i<5; i++) { a[i] = rand() % 10 + 1; }

Even in this case, the time complexity goes quadratic.

Hence the insertion sort is suitable only for the nearly sorted low data elements.

Below table shows the best worst and average case analysis of the program.

N | Best | Worst | Average |

1024 | 0.004 | 0.008 | 0.008 |

2048 | 0.016 | 0.032 | 0.02 |

4096 | 0.048 | 0.116 | 0.084 |

8192 | 0.164 | 0.468 | 0.312 |

16384 | 0.62 | 1.92 | 1.248 |

32768 | 2.47 | 7.704 | 4.94 |

65536 | 9.8 | 30.372 | 19.876 |

131072 | 39.428 | 125.43 | 83.756 |