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

 

Program for Insertion Sort in C++

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

    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 .

    Reply
  2. guatam prajapati

    sorry i didnt say anything because i have fever and headche

    Reply
  3. ankita bagul

    How floating number sorted in insertion sort algorithm. …????
    Please help me. ..

    Reply
  4. Asfand Yar

    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.

    Reply

Leave a Reply

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