In this tutorial I will explain about algorithm for insertion sort in C and C++ using program example. The insertion sort inserts each element in proper place. The strategy behind the insertion sort is similar to the process of sorting a pack of cards. You can take a card, move it to its location in sequence and move the remaining cards left or right as needed.
In insertion sort, we assume that first element A[0] in pass 1 is already sorted. In pass 2 the next second element A[1] is compared with the first one and inserted into its proper place either before or after the first element. In pass 3 the third element A[2] is inserted into its proper place and so on.
Algorithm for Insertion Sort in C & C++
Let ARR is an array with N elements
1. Read ARR
2. Repeat step 3 to 8 for I=1 to N-1
3. Set Temp=ARR[I]
4. Set J=I-1
5. Repeat step 6 and 7 while Temp<ARR[J] AND J>=0
6. Set ARR[J+1]=ARR[J] [Moves element forward]
7. Set J=J-1
[End of step 5 inner
loop]
loop]
8. Set ARR[J+1]=Temp [Insert element in proper place]
[End of step 2 outer
loop]
loop]
9. Exit
Program for Insertion Sort in C
#include<stdio.h>
int main()
{
int i,j,n,temp,a[30];
printf("Enter the number of elements:");
scanf("%d",&n);
printf("\nEnter the elements\n");
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
}
for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j]; //moves element forward
j=j-1;
}
a[j+1]=temp; //insert element in proper place
}
printf("\nSorted list is as follows\n");
for(i=0;i<n;i++)
{
printf("%d ",a[i]);
}
return 0;
}
Program for Insertion Sort in C++
#include<iostream>
using namespace std;
int main()
{
int i,j,n,temp,a[30];
cout<<"Enter the number of elements:";
cin>>n;
cout<<"\nEnter the elements\n";
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=1;i<=n-1;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j]; //moves element forward
j=j-1;
}
a[j+1]=temp; //insert element in proper place
}
cout<<"\nSorted list is as follows\n";
for(i=0;i<n;i++)
{
cout<<a[i]<<" ";
}
return 0;
}
Complexity of Insertion Sort in C & 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).
You should change while statement
while((temp=0)) —> while ((j >= 0) && (temp<arr[j]))
no bro
thank you! It helps me a lot!
it’s gud ,but you have to explain more
THANKS A LOT !!!!!!! IT HELPS ME VERY MUCH
please can you modify it add 2 more things.
1. duplicates values are not allowed.
2.if you enter array size greater than current size of an array it display a message that you enter large size array and again we have to choose the size unless we have chose right.
suppose you decleare an array a[12] and you chose array size 13 it is an error .
you can store the array size dynamically.
You mean I have to create a heap to store the sorted elements ?
sorry i didnt say anything because i have fever and headche
How floating number sorted in insertion sort algorithm. …????
Please help me. ..
Please describe the best case algo
thanks it helps me.
why is not working?
because its not in the mood to work
from the sorted list is not working?
it says cant build project (i use code blocks)
how to print each iteration?
Bro, I need merge sort also..
can we write a[i]=a[j]; inside the while loop instead of a[j+1]=a[j];
if not ? why,,,,
please explain
I have an error at (i=0;i<n;i++)
The last part
Why there is j=j-1?
could you please implement Insertion Sort and Merge Sort in a single source file. You are required to note the time Merge Sort and Insertion Sort takes. Actually this is my assignment. I’ll be very thankful to you.
How to specify space between the elements