Insertion sort algorithm in C language

Insertion sort is used when number of elements is small. It can also be useful when input array is almost sorted, only few elements are misplaced in complete big array.
Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Following are the steps involved in insertion sort:

1. We start by making the second element of the given array, i.e. element at index 1, the key. The key element here is the new card that we need to add to our existing sorted set of cards(remember the example with cards above).
2. We compare the key element with the element(s) before it, in this case, element at index 0:
   • If the key element is less than the first element, we insert the key element before the first element.
   • If the key element is greater than the first element, then we insert it after the first element.
3. Then, we make the third element of the array as key and will compare it with elements to it's left and insert it at the right position.
4. And we go on repeating this, until the array is sorted.

Let's consider an array with values {5, 1, 6, 2, 4, 3}


code .......

// Insertion sort algorithm in C language
#include <stdio.h>
int main()
{
  int a[5]={4,2,0,6,1},n=5,i,j,temp;
  //start sorting
  for(i=1;i<n;i++){
    j=i;
    while(j>0 && a[j-1] > a[j]){
      temp = a[j];
      a[j]= a[j-1];
      a[j-1] = temp;
      j--;
    }
  }
  // Print array
  for(i=0;i<n;i++){
    printf("%d\n", a[i]);
  }
  return 0;
}

if you have any query comment below ...