Posts Tagged ‘insertionsort’

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

Advertisements

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