C program for sorting an array using Insertion Sort technique.

Posted by Mangesh on March 16, 2018

/* Insertion Sort */

Description :

Insertion sort in a sorting algorithm which takes input as array of number and returns the array in sort order as output.
This algorithm is not something uncommon to the persons who know card playing. In the game of cards, a player gets 13 cards. He keeps them in the sorted order in his hand for his ease. A player looks at the first two cards, sorts them and keeps the smaller card first and then the second. Suppose that two cards were 9 and 8, the player swap them and keep 8 before 9. Now he takes the third card. Suppose, it is 10, then it is in its position. If this card is of number 2, the player will pick it up and put it on the start of the cards. Then he looks at the fourth card and inserts it in the first three cards (that he has sorted) at a proper place. He repeats the same process with all the cards and finally gets the cards in a sorted order. Thus in this algorithm, we keep the left part of the array sorted and take element from the right and insert it in the left part at its proper place. Due to this process of insertion, it is called insertion sorting.

Program :

#include<stdio.h>
#include<conio.h>
void InsertionSort(int arr[],int n)
{
int j,i,key;
  for(j=1;j<n;j++)
  {
    key = arr[j];
    i=j-1;
    while(i>=0 && arr[i]>key)
    {
      arr[i+1]=arr[i];
      i--;
    }
    arr[i+1]=key;
  }
}
void printarray(int arr[],int n)
{
int i;
    for(i=0;i<n;i++)
    {
      printf("%d ",arr[i]);
    }
}
void main()
{
int arr[10];
int i,n;
    printf("Enter the total number of element: ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
      printf("Enter %d number in array:",i+1);
      scanf("%d",&arr[i]);
    }
    printf("\n_________Before Insertion Sort__________\n\n");
    printarray(arr,n);
    InsertionSort(arr,n);
    printf("\n\n_________After Insertion Sort__________\n\n");
    printarray(arr,n);
getch();
}

Output :

C program for insertion sort tested in Turbo C 3.2

Written with from Mangesh.

Related Post
1 C program sort array using Bubble Sort technique.
2 C program for sorting an array using Insertion Sort technique.
3 C program to sort an array using Selection Sort technique.
Latest Post
1 shubhanshu
2 test
3 C program for Breadth First Search.
4 C program for Depth First Search(DFS).
5 C for circular queue using linked list.