Algorithm Analysis and Data Structures | Insertion Sort


Theory

In insertion sort we will scan the elements to be sorted with a pointer(say i) from left to right.

Every element on the left of i would have sorted and elements on right have to be sorted.

For every incremental in i pointer, we will use another pointer(say j) to scan form i to its left.

With every step of of j form i to left side of i, compare the jth and (j-1)th element.

If jth element is less than (j-1)th element swap both of them and step down the j for next comparison .

Continue the same till it finds jth element is greater than or equal to (j-1)th element.

If its finds jth element is greater than or equal to (j-1)th element, again increment the i pointer and do the same left traversal with j pointer starting form new i location to its left.

Code


N = 5;
a[] = {1, 6, 4, 3, 6}; //Array with number of elements N =5

for (int i = 0; i < N; i++) //i pointer loop to scan from left to right
{
for (int j = i; j > 0; j--) //j pointer loop to scan from i to its left
{
if( a[j] < a[j-1] ) swap(a, j , j-1); // function to exchange elements if a element is greater than its previous/left one
else break; // to break j pointer loop once the all element of i pointer is get sorted
}
}

In selection sort, the pointer used for find smallest element from unsorted region has to traverse through all the elements for choosing smallest one.

On every rise in steps of pointer which differentiates sorted and unsorted region, there will be a net time complexity about N2/2

But in insertion sort the number of operations for traversal, to insert a element in right position in sorted region will always depends on to up to what extent the given elements had already been sorted.

On an average, half of the elements in sorted region takes part in comparison operation on every incremental steps of pointer which distinguishes between sorted and unsorted regions.

So net time complexity will be about N2/4. Twice as faster than selection sort.

When insertion sort apply on elements which are already sorted, it gives best case output with a simple N number of comparison.

And it performs worst of order ~ N2/2 for reversely sorted set of input.

Comments