Insertion Sort asymptotic Analysis

Posted: January 2, 2015 in Programming
Tags: , , , , , , , , , , ,

insertionSortCard

Best example of insertion sort is sorting deck of cards. .. As you see in the figure, say we have 2,4,5 10 and 7 clubs in our hand and we have to sort it .
As we know, we will take 7 clubs and place it between 5 and 10 clubs. Hence, for each card we need to swap the cards before it and place the key card in place .

 

Before the analysis , lets have a look at pseudo code of insertion sort. For input array A

 


INSERTION-SORT(A)

for j <-- 2 to length [A]

do key <-- A[j]

i <-- j - 1

while i > 0 and A[i] > key

do A[i + i] <-- A[i]

i <-- i - 1

A[i + 1] <-- key

&nbsp;

 

I tried implementing the same in C++. Here is the code

 

 

#include <iostream>

using namespace std;

int main()
{
int arr[] = {5,2,4,6,1,3};
int arrSize =  sizeof(arr)/sizeof(arr[0]);
int key;
int i;
for(int j=1; j<arrSize; j++)
{
        key = arr[j];
        i = j - 1;
        while(i >= 0 && arr[i] > key)
        {
                arr[i+1] = arr[i];
                i = i - 1;
        }   

        arr[i+1] = key;

}

for(int i=0; i<arrSize; i++)
cout << arr[i] << " " << endl;
return 0;
}

Output is :

insertionSortOutput

Before we start our analysis of the insertion sort, we will see how many times each statement runs.

 


INSERTION-SORT(A)

for j <-- 2 to length [A] ----------------------------  runs n times

do key <-- A[j] --------------------------------------  runs n-1 times

i <-- j - 1     --------------------------------------  runs n-1 times
                                                       n
while i > 0 and A[i] > key --------------------------- ∑ tj
                                                       j=2
                                                       n
do A[i + i] <-- A[i]  -------------------------------- ∑ tj - 1
                                                       j=2

                                                       n
i <-- i - 1 ------------------------------------------ ∑ tj - 1
                                                       j=2
A[i + 1] <-- key ------------------------------------- n-1

&nbsp;

Now, lets get into the analysis part.
Okay, In each statement , we do some operations as well i.e – increment, decrement, counter — all those are considered to be constants. Hence we name constants from c1 to c7
And also, tj is the function which does while loop operation .
If the input is already sorted, there would be no in-swapping takes place. i.e. While loop will never be executed. Since while loop is inside FOR loop which runs from 2 to n , we enclose it with sigma j = 2 to n.
Hence the equation would be
What could be the Best case ?? — A sorted input
and what could be the worst case input . — Input sequence in reverse order.

 

These 3 screenshots will explain how insertion sort is O(n) in best case and O(n square) in worst case. 

 

 

BestCase

insertion_sort

worst case

 

This you tube video will be helpful to understand the same

https://www.youtube.com/watch?v=yXwFrc5GS6A — click the view the video 

 

Advertisements

Comments are closed.