Insertion Sort step By step explanation and operatons

Insertion Sort

It is one of the well known sorting algorithm which is really effective when it comes to sort small number of elements. 

Insertion Sort's real life co-relation

• Its implementation is similar to the way one might sort hand of king higher playing cards.
• Initiate with an empty left hand and cards face down on the table.
• Pick one card at once from the table and insert it at its rightful place in the left hand.
• In order to find the correct position of  a card, compare it with all the cards already present in the left hand in the right to left direction.
• Note at all times the cards in the left hand are always sorted.

Let us try to understand insertion sort with the help of an example..... 

Suppose we have a list of 10 numbers as: 10,32,5,3,98,87,90,45,1,49

1. Let us start from 10, Since there is nothing in the left hand so we will directly put 10 in our left hand.
2. Next we'll pick 32 from the table, and compare it with 10, since it is larger than 10 so its position will be after 10 in our left hand.
3. Now the next number is 5, We'll compare from right to left till we get a number smaller than 5 or we reach the end of the list i.e the left most end, since 5 is smaller than 32 so 32 will be shifted at 5's place,again 5 is smaller than 10 also,hence 10 will be shifted at 32's place,and now we reach the left most end and hence will place 5 over there,so finally there are 5,10,32 on the left hand and 3,98,87,90,45,1,49 on the table.
4. Next we'll pick 3, and compare it from right to left direction, after comparing we'll get 3,5,10,32 in the left hand and rest on the table.
5. Picking up 98 we don't have any number smaller than this,hence will place 98 at the right most end of left hand making the new list in left hand as 3,5,10,32,98.
6. 87 the next number to be inserted before 98 in the left hand making the list as 3,5,10,32,87,98.
7. 90 to occupy the position after 87 and before 98, making left hand list as, 3,5,10,32,87,90,98.
8. 45 to be picked next from table will be placed after 32 and before 87 to update the list as, 3,5,10,32,45,87,90,98.
9. 1 to be placed at the beginning updated the list as 1,3,5,10,32,45,87,90,98.
10. Finally the last number on the table to be placed between 45 and 87, making the final sorted list as: 1,3,5,10,32,45,49,87,90,98.

Insertion Sort Passes

Source Code:

#include<stdio.h>

# define MAX 20

void main()

{

    int soin[MAX],i,j,n,k,swap_var,key;

    printf("Enter the number elements needs to be sorted:");

    scanf("%d",&n);

    printf("\nEnter the list of %d,you want to sort:",n);

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

    {

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

    }

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

    {

        key=soin[i];

        j=i;

        while(j>=1&&key<soin[j-1])

        {

                soin[j]=soin[j-1];                       

            j--;

        }

        soin[j]=key;                                       // Key inserted at its proper place

        printf("\nAfter pass %d list is",i);

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

            printf(" %d",soin[k]);                    //Just for display purpose

    }

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

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

    {

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

Note use of macros is recommended so that code can be made flexible.