Insertion sort

 Sorting is a process of rearranging the data items in ascending or descending order.Here the data items are shifted from one location to the other.

Insertion sort is implemented by inserting a particular element(single element) at the appropriate position. In this method, the first iteration starts with comparison of 1’s element(second element) with the 0’s element(first element). In the second iteration 2nd element(third element) is compared with the 0’s and 1’s element.

 

 In general, in every iteration an element is compared with all elements before it. During comparison, if is found that the element in question can be inserted at a suitable position, then space is, related to it by shifting the other elements one position to the right and inserting the element at the suitable position. This procedure is repeated  for all the elements in the array.

#include<stdio.h>

void main()

  {

     int A[20],N,Temp,i,j;

     clrscr();

  

     printf("\n Enter the number of terms......:");

     scanf("%d",&N);

     printf("\n Enter the elements of the Array....:");

     for(i=0;i<N;i++)

      {

        /*gotoxy(25,11+i);    */

        scanf("%d",&A[i]);

      }

     for(i=0;i<N;i++)

     {

        Temp=A[i];

        j=i-1;

        while(Temp<A[j] && j>=0)

         {

            A[j+1]=A[j];

            j=j-1;

         }

       A[j+1]=Temp;

    }

     printf("\n The ascending order list is....:");

     for(i=0;i<N;i++)

     printf("\n%d",A[i]);

     getch(); //insort.c

  }

Output....

insertion sort

Another Example…

/* Program of sorting using insertion sort (insert~1.c)*/

#include <stdio.h>

#define MAX 20

main()

{

                int arr[MAX],i,j,k,n;

                printf("Enter the number of elements : ");

                scanf("%d",&n);

                for (i = 0; i < n; i++)

                {

                                printf("Enter element %d : ",i+1);

                                scanf("%d", &arr[i]);

                }

                printf("Unsorted list is :\n");

                for (i = 0; i < n; i++)

                                printf("%d ", arr[i]);

                printf("\n");

                /*Insertion sort*/

                for(j=1;j<n;j++)

                {

                                k=arr[j]; /*k is to be inserted at proper place*/

                                for(i=j-1;i>=0 && k<arr[i];i--)

                                                arr[i+1]=arr[i];

                                arr[i+1]=k;

                                printf("Pass %d, Element inserted in proper place: %d\n",j,k);

                                for (i = 0; i < n; i++)

                                                printf("%d ", arr[i]);

                                printf("\n");

                }

                printf("Sorted list is :\n");

                for (i = 0; i < n; i++)

                                printf("%d ", arr[i]);

                printf("\n");

}/*End of main()*/

Output.....

Insertion Sort