Simplifying The Complexities: Insertion-Sort with running time O(n lg(n))

Simplifying The Complexities: Insertion-Sort with running time O(n lg(n)): Insertion Sort : Insertions sort , sorts the elements in place in an array with running time O(n2). Below is code of insertion sort with...

Counting inversion : Complexity O(n*lgn) and in=place sort

#include <cstdlib>
#include <iostream>
#include <vector>
#include<fstream>
#include<iomanip>
#include <cstdio>
#include <cstring>
using namespace std;
#define newData unsigned __int64
/*Inversion : it is set of (i,j) where i<j and a[i]>a[j]
Idea is to create an array from large file with inputs of millions .
Then apply in-place merge sort */

void CreateArrayFromFile(vector<long> &aV,string aFileName)
{
 ifstream file;
 char* fileName = new char[aFileName.size()+1];
 strcpy(fileName,aFileName.c_str());
 file.open(fileName,ifstream::in);
 if(!file)
 {
  cout<<"CreateArrayFromFile:File couldn't open: "<<"\n";
   return ;
  }
long  i=0;
  while(!file.eof()){
  long val;
  file>>val;
//  aV.push_back(val);
  aV[i]=val;
  i++;
  }
  free(fileName);
  file.close();
}
/*The mere is tricky for in-place but it saves O(n) space which is used for merging data in merge function.
*/

newData MergeInSort(vector<long> & aVector,long low, long mid,long high)
{
   
long left=low;
long right=mid+1;
newData count=0;
if(aVector[mid]<aVector[right])
   return 0;
 
while((left<=mid) && (right<=high)) {
// left one smaller then no change:
   if(aVector[left]<aVector[right]){
   left++;
   }else{
   long tmp=aVector[right];
 
   for(long index=right;index>left;index--){
   aVector[index]=aVector[index-1];
   count++;    
   }
   aVector[left]=tmp;
   left++;
   right++;
   mid++;
   }
 }
 
return count;
}

newData InPlaceMergeSort(vector<long> &aVector,long low,long high)
{
// base case
if(low>=high)
   return 0;
 
long mid=(low+high)/2;

newData x= InPlaceMergeSort(aVector,low,mid);
newData y= InPlaceMergeSort(aVector,(mid+1),high);  
newData z= MergeInSort(aVector,low,mid,high);

return (x+y+z);

}


int main(int argc, char *argv[])
{

vector<long> aMainArray(100000);
string file("IntegerArray.txt");
CreateArrayFromFile(aMainArray,file);
long size = aMainArray.size()-1;
cout<<"Size: "<<size<<"\n";
cout<<"Inversion: "<<InPlaceMergeSort(aMainArray,0,size)<<"\n";

  system("PAUSE");
  return EXIT_SUCCESS;
}

Ans : 2407905288

Insertion-Sort with running time O(n lg(n))

Insertion Sort :
Insertions sort , sorts the elements in place in an array with running time O(n2).
Below is code of insertion sort with running time O(n2) :


void InsertionSort(vector<int>& aV)
{
int size = aV.size();
for(int i=1;i<size;i++)
 {
  for(int j=0;j<i;j++)
   {
     // Places element i in correct and sorted sub-array 0...(i-1)
     if(aV[i]<aV[j])
     {
      int temp = aV[i]; 
      aV[i]=aV[j];
      aV[j]=temp;
     }
   }
 }
}

Here we can play with above code to improve running time to O(n lg(n)) by using Binary Search.

Instead of inner loop in code mentioned above , Binary Search can be used to search for place of swap and then sort remaining array so that sub-array ( from 0 to (i-1) ) will be sorted.

Please find code below :

/*Insertion Sort with Binary Search Running time : O(n lg(n)) */

void BinarySearchAndSwap(vector<int> &aV,int aIndexTillSorted,int aIndexToSearch)

{

int low =0;

int high =  aIndexTillSorted;

    while(low<=high)

         {

          int mid = (low+high)/2;

          if(aV[mid]>aV[aIndexToSearch])

          {

           if(aV[mid-1]>aV[aIndexToSearch])

              high = mid-1;

           else // swap mid and aIndexToSearch

               {

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid];

                aV[mid]= temp;

                // To sort remaining part of array 

                  low= mid+1;

               }   

          

          }else if(aV[mid]<aV[aIndexToSearch])

          {

           if(aV[mid +1]< aV[aIndexToSearch])

               low = mid+2;

           else{ // Swap mid +1 with aIndexToSearch

                int temp = aV[aIndexToSearch];

                aV[aIndexToSearch] = aV[mid +1];

                aV[mid+1] = temp;

                // To sort remaining part of array 

                low= mid+2;         

                }    

          }        

             

             

          }

}

void InsertionSortWithbinarySearch(vector<int> &aV)

{

int size = aV.size();

    for(int i=1;i<size;i++)

    {

     BinarySearchAndSwap(aV,i-1,i);

    }

}

Khamma Ghani Sa

To all my friends "Khamma Ghani Sa"...

I was born in Jodhpur, the Sun City. It’s famous for its delicious food (that’s all I remember about the heritage city. HENCE PROVED. I am a big foodie). I did my schooling from Jodhpur and graduation from Jaipur. Finally came to my Karma Bhoomi Bangalore. “Karma Bhoomi” because most of the time I stay in office( My wife will not like this I know ). No regrets after all I get paid for it.

Born in Marwar and belong to a traditional yet well educated Marwari family. Obviously, I am supposed to understand and speak Marwari very well.But yesterday when I was talking to my father-in-law over phone.Oh ! before that I want to say he has a very good sense of humor which I like most in him.(It is not just to please my wife ).Lets continue ,  he greeted me with  most of the times heard words "Khamma Ghani Sa" and I replied with "Ghani Ghani Kamma Sa" .

But it left a question in my mind .. What is the actual meaning of this "Khamma Ghani Sa" ?

Today in office , after I signed in to gtalk ... I saw couple of Jodhpuri friends online . Discussed with them about these mystery word ... after discussion and couple of google searches found out its meaning .

Khamma - "Daya or Meeharbani or Mafi" basically forgiveness

Ghani      - "Bahut "

and Sa is use to give respect .

This is basically used to greet elders in Marwari Language .

Next time onwards I'll  make sure that before my father-in-law greet me with these no-more mystery words I will greet him with "Khamma Ghani Sa" .

Thanks to my dear friends Ankur Acharya , Rakesh Harsh, Dheeraj Tanwar with whome i discussed on these words.

A very special thanks to my beautiful and lovable wife for playing the role of editor :).