Insertion Sort

Logic

Each element is picked up and inserted in its proper place.

Passes

Pass 1: Element at position 1 is picked up and inserted at proper place.

Pass 2: Element at position 2 is picked up and inserted at proper place.

|

|

|

Pass n-1: Element at position n-1 is picked up and inserted at proper place.

Passes required:  n-1

Comparisons required:In every pass i,element is compared with maximum i elements(in worst case) and minimum 1 element(in best case).

Note: At end of every pass i,all the elements at positions before it are sorted.

Code

#include<stdio.h>

void ins_sort(int*,int);

int main()
{
        int no,i,arr[25];
        printf("Enter number of elements ");
        scanf("%d",&no);
        printf("\nPlease enter elements to be sorted ");
        for(i=0;i<no;i++)
            scanf("%d",arr+i); 
        ins_sort(arr,no);
        return 0;
}

void ins_sort(int arr[],int no)
{
    int i,ins,j;                      
    printf("\nSorted array = ");

    for(i=1;i<no;i++)
    {
            ins=arr[i];

            for(j=i-1;j!=-1 && ins<arr[j];j--)
                arr[j+1]=arr[j];

            arr[j+1]=ins;

    }
    for(i=0;i<no;i++)
            printf("%d ",arr[i]);

}

More

Time Complexity of Insertion Sort