27.Insertion Sort ~ Bachelor Zone

Logic : Here, sorting takes place by inserting a particular element at the appropriate position, that’s why the name- insertion sorting. In the First iteration, second element A[1] is compared with the first element A[0]. In the second iteration third element is compared with first and second element. In general, in every iteration an element is compared with all the elements before it. While comparing if it is found that the element can be inserted at a suitable position, then space is created for it by shifting the other elements one position up and inserts the desired element at the suitable position. This procedure is repeated for all the elements in the list.

If we complement the if condition in this program, it will give out the sorted array in descending order. Sorting can also be done in other methods, like selection sorting and bubble sorting, which follows in the next pages.

Insertion Sort Program

#include<stdio.h>  
#include<conio.h>  
  
   void insertion(int a[],int n)  
   {  
  
    int i,j,x,k;  
  
           for(i=1;i<=n-1;i++)  
    
                {  
                       j=i;  
  
                       x=a[i];  
  
  
                       while(a[j-1]>x && j>0)  
  
                                 {  
  
                                   a[j]=a[j-1];  
                                    j=j-1;  
  
                                 }  
  
                        a[j]=x;  
  
  
                       printf("\n\n The array after pass no.%d: ",i);  
                       for(k=0;k<=n-1;k++)  
                      printf("%4d",a[k]);  
  
  
                 }//end for.  
  
  
   } //end function.  
  
   void main()  
  
   {  
  
     int a[1000],n,i;  
  
     clrscr();  
  
     printf("\n\nEnter an integer value for total no.s of elements to be sorted: ");  
     scanf("%3d",&n);  
  
     for(i=0;i<=n-1;i++)  
  
          {  
  
            printf("\n\nEnter an integer value for element no.%d: ",i+1);  
            scanf("%4d",&a[i]);  
  
          }  
  
  
     insertion(a,n);  
  
  
     printf("\n\n\nFinally sorted array is : ");  
     for(i=0;i<=n-1;i++)  
     printf("%4d",a[i]);  
  
  
   }//end program.  
  
/*

OUTPUT:

Enter an integer value for total no.s of elements to be sorted: 6

Enter an integer value for element no.1: 67

Enter an integer value for element no.2: 34

Enter an integer value for element no.3: -23

Enter an integer value for element no.4: 100

Enter an integer value for element no.5: 0

Enter an integer value for element no.6: -68

The array after pass no.1: 34 67 -23 100 0 -68

The array after pass no.2: -23 34 67 100 0 -68

The array after pass no.3: -23 34 67 100 0 -68

The array after pass no.4: -23 0 34 67 100 -68

The array after pass no.5: -68 -23 0 34 67 100

Finally sorted array is : -68 -23 0 34 67 100