Insertion Sort in C & C++ – Program & Algorithm

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]
8. Set ARR[J+1]=Temp [Insert element in proper place]
 [End of step 2 outer
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;
}
 
C/C++ Program and Algorithm for Insertion Sort

 

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

23 thoughts on “Insertion Sort in C & C++ – Program & Algorithm”

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

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

Leave a Comment

Your email address will not be published. Required fields are marked *