Insertion Sort

Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n²).

Working of Insertion Sort:
Insertion sort work same as player of playing card places upcoming card at its proper sequence.

• Start from pointing first and second element in an array.
• If second element of array is lesser than first element then swap position of those two element.
• Increment the pointer and check for all element sequentially and place each upcoming element to proper sequence in an array till last element of array.

Entered Array is :'111' '12'    '45'    '13'    '78'    '80'
 Sorted Array after 1 pass:'12' '111'   '45'    '13'    '78'    '80'
 Sorted Array after 2 pass:'12' '45'    '111'   '13'    '78'    '80'
 Sorted Array after 3 pass:'12' '13'    '45'    '111'   '78'    '80'
 Sorted Array after 4 pass:'12' '13'    '45'    '78'    '111'   '80'

 Sorted Array after 5 pass:'12' '13'    '45'    '78'    '80'    '111'    

library declaration:
 #include<stdio.h>
#include<stdlib.h>

Prototype Declaration:
int insertionsort(int*,int);
void display(int* ,int);

Main Program:
int main()
{
    int *arr,i,n;
    printf("Enter the no. of elements\n");
    scanf("%d",&n);
    arr=(int*)malloc(n*sizeof(int));
    printf("Enter elements\n");
    for(i=0;i<n;i++)
        scanf("%d \t",(arr+i));
printf("\nEntered Array is :");
display(arr,n);
insertionsort(arr,n);
printf("\nFinally sorted Array is :");
display(arr,n);
return 0;
}

C Function For Insertion Sort:
int insertionsort(int *arr,int n)
{
    int i,j,temp;
for(i=1;i<n;i++)
    {
        temp=*(arr+i);
        j=i-1;
        while(temp<*(arr+j)&&j>=0)
        {
            *(arr+(j+1))=*(arr+j);
            j--;
        }
        *(arr+(j+1))=temp;
        printf("\n Sorted Array after %d pass:",i);
        display(arr,n);
     }
    return 0;
}

C Function For Display Array:
void display(int *arr,int n)
{ int i=0;
  for(i=0;i<n;i++)
printf("\'%d\'\t",*(arr+i));
}