Wednesday, 28 March 2012

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




No comments:

Post a Comment