Posts Tagged ‘worst’

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

In my past post , i explained the insertion sort with c++ code

https://shrinathsuccess.wordpress.com/2014/03/09/insertion-sort-c/

The major overhead in the insertion sort algorithm is swapping. For each element we are performing j-i swaps if the sequence is in descending order. Swaps are much costlier and we also need a new variable involved for swapping. If we could reduce the number of swapping then we will hit with the better performance.


#include <iostream>
#include <stdlib.h>
using namespace std;
int main()
{
        cout << "Enter number of elements" << endl;

        int n,i,j;
        cin >> n;
        int a[n];
        int c = 0;
        srand(time(NULL));
        for(i=n; i>0 ; i--)
        {
                a[c] = i;
                c++;
        }
        cout << "Array Before Sorting" << endl;
          for(int i=0 ; i<5; i++)
          cout << a[i] << endl;
        for(i=1 ; i<n ; i++)
        {
                int key = a[i];

                for(j=i ; j>0 ; j--)
                {
                        if(a[j-1] > key)
                        {
                                a[j] = a[j-1];
                        }
                }
                a[j] = key;
        }

        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

TRIAL :

5 4 3 2 1

i = 1
key = 4
j = 1 , 1> 0

if(a[0] > key) => if(5 > 4)
a[1] = a[0] => 5 5 3 2 1

j=0 ; 0>0 – false
end of inner for loop
a[0] = key => 4 5 3 2 1
i=2
key = 3
j = 2

i = 2
key = 3
j = 2 ; 2 > 0
if(a[1] > key) => if(5 > 3)
a[2] = a[1] => 4 5 5 2 1

j=1 ; 1>0
if(a[0] > key) => if(4 > 3)
a[1] = a[0] => 4 4 5 2 1

j=0 ; j>0 – false
a[0] = 3 => 3 4 5 2 1

and the loop goes on like this ….

Instead of swapping the elements we perform assignment operation and at the end of the loop we assign the key back to the right place.

Special thanks to Nithin for pointing this out – https://www.facebook.com/nithin.kalathingal.5

WHAT IS INSERTION SORT :

Insertion sort is a sorting algorithm which sorts the input data by putting elements into the sorted array one at a time .

It compares the next element in the array and puts it in the right place .

                                   Insertion Sort Graph


WHY INSERTION SORT :

When there are couple of sorting algorithms available why should i hit insertion sort ???

When the number of elements to be sorted is much lower , insertion sort gives us a very good result compared to others. Hence use it when the data set is low.

HOW INSERTION SORT WORKS :

Lets take an input tape with 5 elements in descending order.

5 4 3 2 1

4 5 3 2 1

3 4 5 2 1

2 3 4 5 1

1 2 3 4 5

On each iteration , it takes one element at a time and compares with the next element and places it in the right position.

First Iteration we take 4 as Key element . compare it with 5 . Since 4 is lesser we swap 4 and 5.

Second Iteration we take 3 as Key element . compare it with 5. 3 is lesser than 5 . Swap it . Yes, 3 is lesser than 4 also . Hence continue the swap until you place the element in the right place.

CODE FOR INSERTION SORT :


#include <iostream>
using namespace std;
void swap(int &a, int &b);

int main()
{
        // initializing the variables
        int a[10000];
        int c = 0;
        int n;

        // insert elements in descending order
        cin >> n;
        for(int i=n ; i>0; i--)
        {
        a[c] = i;
        c++;
        }

        // print the array before sorting
        cout << "Array Before Sorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;

        // insertion sort logic starts here
        for(int i=0 ; i<n-1; i++)
        {
                int key = a[i+1];
                int pos = i+1;
                for(int j=i; j>=0 ;j--)
                {
                        if(a[pos] < a[j])
                        {
                                swap(a[pos],a[j]);
                                pos--;
                        }
                }
        }
        // insertion sort logic ends here. Printing the array after sort.
        cout << "Array AfterSorting" << endl;
        for(int i=0 ; i<n; i++)
                cout << a[i] << endl;
        return 0;
}

void swap(int &a, int &b)
{
        int t;
        t = a;
        a = b;
        b = t;

}

EXPLANATION :

for(int i=0 ; i<n-1; i++)

Each time we need to pick an element and put it in the right place. Hence we need a loop that runs through an array.

int key = a[i+1];
int pos = i+1;

On each iteration we choose one element as key and place it in the right place.
Hence , we are choosing the element which is in i+1 place as key and noting down its position in variable pos.

for(int j=i; j>=0 ;j–)

This innner for loop helps to compare the previous elements . we need to check till the first element and place the key element at the right place.

if(a[pos] < a[j])
{
swap(a[pos],a[j]);
pos–;
}

This condition checks with the previous element . If it is greater then it swaps the element .

TRIAL

Lets run this program for 5 elements .

Now input tape contains 5 4 3 2 1

First Iteration :

i=0 , key = 4, pos = 1
j=0 , 0>=0 is true hence
if(4<5) swap(4,5); pos– => pos = 0
Now, input tape contains : 4 5 3 2 1

Second Iteration:

i=1, 1<5, key = 3 and pos = 2 j=1, 1>=0
if(3<5) – true swap(3,5); Now input tape contains 4 3 5 2 1 pos — => pos =1

j– => j=0
j=0; 0>=0
if(3 < 4) – true swap(3,4) pos– = > pos = 0
Now input tape contains 3 4 5 2 1

Simillary loop goes on sorting .

BEST , WORST AND AVERAGE CASES

The program given above is for worst case . since the elements are in descending order . In this case, we need to compare all the elements with 2 for loops . The time complexity will be quadratic

For Best case scenario put the elements in the sorted order.

 for(int i=0 ; i<5; i++)
        a[i] = i+1;

Eventhough the elements are in the sorted order, the outer for loop will be running for n comparisons. Hence the best case is O(N);

AVERAGE CASE :

Generate random numbers and insert it into array .

#include <stdlib.h>
 srand(time(NULL));
         for(int i=0 ; i<5; i++)
        {
                a[i] = rand() % 10 + 1;
        }

Even in this case, the time complexity goes quadratic.
Hence the insertion sort is suitable only for the nearly sorted low data elements.
Below table shows the best worst and average case analysis of the program.

N Best Worst Average
1024 0.004 0.008 0.008
2048 0.016 0.032 0.02
4096 0.048 0.116 0.084
8192 0.164 0.468 0.312
16384 0.62 1.92 1.248
32768 2.47 7.704 4.94
65536 9.8 30.372 19.876
131072 39.428 125.43 83.756