#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