Posts Tagged ‘faster’

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