C program to implement Insertion Sort

Here a C  program  to implement  insertion  sort is given, insertion sorting technique is the elementary sorting technique. Insertion sort sorts one element at a time, It is just like manual sorting by humans. Insertion sort is better for small set of elements. Insertion sort is slower than heap sort, shell sort, quick sort,and merge sort.

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

C  program  to implement  Insertion  Sort

#include <stdio.h>
void insertion_sort();
int a[50],n;

main()
{
 int i;
 printf("nEnter size of an array: ");
 scanf("%d", &n);
 printf("nEnter elements of an array:n");
 for(i=0; i<n; i++)
 scanf("%d", &a[i]);
 insertion_sort();
 printf("nnAfter sorting:n");
 for(i=0; i<n; i++)
 printf("n%d", a[i]);
 getch();
}

void insertion_sort()
{
 int j, k, temp;
 for(j=1; j<n; j++)
 {
  temp = a[j];
  k = j-1;
  while (k>=0 && a[k]>temp)
  {
   a[k+1] = a[k];
   k--;
  }
  a[k+1] = temp;
 } 
}

Output

Enter size of an array:10
Enter elements of an array:23 43 56 34 12 34 55 65 76 21
After sorting:12 21 23 34 34 43 55 56 65 76