Insertion Sort in C


In insertion sort we insert a particular element at the appropriate position. We start with the 1st element and then compare it with the 0th element. Then we take 2nd element and we compare it with the 0th element followed by 1st element. If the element which is to be compared is smaller than any element before it then we move all elements before that element to one place right and we shift the main element to appropriate position.

Steps

  1. Start with 1st element and compare it with 0th element. If the 1st element is smaller than the 0th element then shift the 0th element to one place right and the 1st element to 0th place.

     
  2. Now move to 2nd element. Compare the 2nd element with 0th element.
    If the 2nd element is smaller than the 0th element then move 2nd element to 0th position and shift all elements before 2nd position to one place right.
    But, if the 2nd element is larger than the 0th element then compare the 2nd element with 1st element and repeat the same step.
     

Create an array

int a[5] = {2, 5, 1, 13, 9};

Shift element to one position right

  for(k=i;k>j;k--){
            a[k] = a[k-1];
         }

Check each element before current element to find a appropriate position

   for(i=1; i<5; i++){
       for(j=0; j<i; j++){
        if(a[i]<a[j]){
            temp = a[j];
            a[j]= a[i];
         for(k=i;k>j;k--){
            a[k] = a[k-1];
         }
         a[k+1] = temp;      
        }
        
       }
   }

Complete code

#include <stdio.h>
#include <string.h>

main()
{
   int a[5] = {2, 5, 1, 13, 9};
   int i, temp, j, k, t;
   for(i=1; i<5; i++){
       for(j=0; j<i; j++){
        if(a[i]<a[j]){
            temp = a[j];
            a[j]= a[i];
         for(k=i;k>j;k--){
            a[k] = a[k-1];
         }
         a[k+1] = temp;      
        }
        
       }
   }
   for(i = 0;i<5;i++){
   printf("%d, ", a[i]);
   }
}

Output: