### What is Insertion Sort:

Insertion Sort is really simple, just take the number, compare it with all the elements on its left and place it at its proper place. For example in case of playing cards you pick the card and compare it with all the sorted cards and place it at its exact place.

**The program is compiled using g++ compiler on windows.**

Let’s see a graphical view of how insertion sort works:

### How Insertion Sort works in graphical way:

### Algorithm:

Let ARR is an array with N elements

- Read ARR
- Repeat step 3 to 8 for I=1 to N-1
- Set Temp=ARR[I]
- Set J=I-1
- Repeat step 6 and 7 while Temp<ARR[J] AND J>=0
- Set ARR[J+1]=ARR[J] [Moves element forward]
- Set J=J-1

[End of step 5 inner

loop]

- Set ARR[J+1]=Temp [Insert element in proper place]

[End of step 2 outer

loop]

- Exit

### Complexity in Best, Average and Worst Case:

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 remaining element 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 before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(*n*^{2})).

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.

### C++ Program:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
#include <iostream> using namespace std; int main() { int a[16], i, j, k, temp; cout<<"enter the elementsn"; for (i = 0; i < 5; i++) { cin>>a[i]; } for (i = 1; i < 5; i++) { for (j = i; j >= 1; j--) { if (a[j] < a[j-1]) { temp = a[j]; a[j] = a[j-1]; a[j-1] = temp; } else break; } } cout<<"sorted arrayn"<<endl; for (k = 0; k < 5; k++) cout<<a[k]<<endl; } |

### OUTPUT:

### Complexity of Insertion Sort in C++:

There is 1 comparison during pass 1 for proper place. There are 2 comparisons during pass 2 for proper place. There are 3 comparisons during pass 3 for proper place, and so on accordingly.

F(n) = 1 + 2 + 3 + . . . . + (n-1) = n (n-1)/2 = O(n^{2})

Hence complexity for insertion sort program in C and C++ is O(n^{2}).

Please comment if you face any problem.

## Leave a Reply