Insertion Sort

C Implementation of "Insertion Sort"

Insertion Sort:

1. Has a Time Complexity of O(n^2)
2. Better than Bubble Sort & Selection Sort
3. Logic:
• Divide the array into sorted part & unsorted part
• Create a hole in unsorted part, and copy that element to a variable 
• Compare the value with each and every value in unsorted part
• If the values in the Sorted part is found to be greater than this value, do a shift
• Place the copied value in the created hole in the sorted part after all the shifts

#include <stdio.h> #include <stdlib.h> /* Function insertion sort */ void insertionsort(int a[],int n) { int i,temp,hole,j; /* for the range of 1 to n-1 in the array a */ for(i=1;i<n;i++) { /* copy the element from the unsorted part, which creates an imaginary hole */ temp=a[i]; /* Keep track of the index of the hole created */ hole=i; /* Until we have a hole greater than the starting index & the value in the sorted part is lesser than the copied value */ while(hole>0 && a[hole-1]>temp) { /* shift the values to the hole, that creates another hole in the array */ a[hole]=a[hole-1]; /* so, keep track of the hole in the array */ hole=hole-1; /* Uncomment the following lines to see the results after every pass */ for(j=0;j<n;j++) printf("%d ",a[j]); printf("\n"); } /* Copy the value which we copied to temp earlier, to the place where it is intended to be */ a[hole]=temp; for(j=0;j<n;j++) printf("%d ",a[j]); printf("\n"); } } int main(void) { /* Input unsorted array */ int a[]={5,4,2,3,1}; int i; /* Function call to perform insertion sort passing array starting address & size of the array */ insertionsort(a,5); /* Printing the sorted array */ for(i=0;i<5;i++) printf("%d ",a[i]); return 0; }