Sorting program #3 : Insertion sort !

Insertion_sort(k,N): Vector K with N elements

Brief Explanation :

    Here we maintain our array in two sub-arrays , i.e. 1. Sorted 2. Unsorted
    Initially , first element is the only member of sorted array.
    Then we move further , pick next element i.e. first element of the unsorted array and insert it to appropriate position .

    This is how , the sorted array is growing and unsorted is shrinking with every pass and hence at last the whole array is sorted .

---

ALGO :-

  o) PASS - pass number and index of first unsorted data
  o) HOLE - Index of element to be pick up for insertion
  o) VALUE - The element to picked up for insertion

---

step 1 : [loop on PASS index]
    Repeat thru step 4 for PASS = 1,2,...,N
   
step 2 : [Initialize VALUE and HOLE]
    VALUE <- K[PASS]
    HOLE <- PASS

step 3 : [Inserting the current value in sorted sub-array at appropriate index]
    Repeat steps 3.1 and 3.2 while HOLE>0 and K[HOLE-1]>VALUE
   
    3.1 : [Shifting the greater element to right side]
        K[HOLE] <- K[HOLE-1]
    3.2 : [Shifting the index HOLE to left ]
        HOLE <- HOLE-1

step 4 : [Inserting value after necessary shifts made]
    K[HOLE] <- VALUE
       
step 4 : [Finished] 

---

By following algorithm you can easily implement a program for it . Else , You can refer the following code and check the implementation !

---

Implementation of Insertion sort in C : 

---

#include<stdio.h>
#define max 200

int main()
{   
    int a[max],n,i;   
    printf("Enter the number of elements : ");
    scanf("%d",&n);
    printf("Enter array elements :\n");
    for(i=0;i<n;i++)
    {
        scanf("%d",&a[i]);   
    }
   
    //insertion sort
    int value,hole,k;
    for(k=1;k<n;k++)
    {
        value = a[k];/*Here a[k] is the element which is to be inserted into sorted part*/
        hole = k;
        while(hole>0 && a[hole-1]>value)//shifting all greater elements
        {
            a[hole] = a[hole-1];
            hole--;
        }
        a[hole] = value;/*now, hole is the perfect index where we can insert the value.*/
    }   
    printf("Array : ");
    for(i=0;i<n;i++)
    {
        printf(" %d ",a[i]);   
    }
    printf("\n");
}

---

Thanking you !