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

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 35 36 |
#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++

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 35 36 37 38 |
#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(n

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

^{2}).
MonirulYou should change while statement

while((temp=0)) —> while ((j >= 0) && (temp<arr[j]))

surajno bro

kerine lynthank you! It helps me a lot!

ashokit’s gud ,but you have to explain more

SIDRATHANKS A LOT !!!!!!! IT HELPS ME VERY MUCH

Hamzaplease 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 .

Vijay Kumar Sharmayou can store the array size dynamically.

zaidYou mean I have to create a heap to store the sorted elements ?

guatam prajapatisorry i didnt say anything because i have fever and headche

ankita bagulHow floating number sorted in insertion sort algorithm. …????

Please help me. ..

Vijay Kumar SharmaPlease describe the best case algo

kunal anandthanks it helps me.

m0maywhy is not working?

shyinabecause its not in the mood to work

m0mayfrom the sorted list is not working?

benakit says cant build project (i use code blocks)

sreeramhow to print each iteration?

Sakhawat AkibBro, I need merge sort also..

[email protected]can we write a[i]=a[j]; inside the while loop instead of a[j+1]=a[j];

if not ? why,,,,

please explain

EmiliaI have an error at (i=0;i<n;i++)

The last part

Pranav SureshWhy there is j=j-1?

Asfand Yarcould 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