How to implement insertion sort in C++?
Insertion Sort in C++ 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 for Insertion Sort:
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
- Set ARR[J+1]=Temp [Insert element in proper place]
[End of step 2 outer
Program to implement Insertion Sort in C++:
using namespace std;
int a, i, j, k, temp;
cout<<"enter the elementsn";
for (i = 0; i < 5; 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;
for (k = 0; k < 5; k++)
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(n2)
Hence complexity for insertion sort program in C and C++ is O(n2).
Please comment if you face any problem.