Algorithms: Design and Analysis, Part 1 Programming Question-1

CountInversions .cpp

#include <iostream>
#include <fstream>
#include <vector>
using namespace std;

unsigned int merge(vector<int>&nums,int begin,int middle,int end)
{
    vector<int> left(nums.begin()+begin,nums.begin()+middle);
    vector<int> right(nums.begin()+middle,nums.begin()+end);

    int l=0,r=0;
    unsigned int count=0;
    while(l<left.size()&&r<right.size())
    {
        if(left[l]<right[r])
        {
            nums[begin++]=left[l++];
        }
        else
        {
            count+=(left.size()-l);//count inversions of sequence
            nums[begin++]=right[r++];
        }
    }
    while (l<left.size()) nums[begin++]=left[l++];

    while (r<right.size())nums[begin++]=right[r++];

    return count;
}
/*
using merge sort to count inversions of sequence
*/
unsigned int countInversions(vector<int> &nums,int begin,int end)
{
    if(begin>=end-1)return 0; //[begin,end) 距离小于等于1 时就要返回，否则最后会出现循环调用[0,1)
    int mid=(begin+end)/2;
    unsigned int lcount=countInversions(nums,begin,mid);
    unsigned int rcount=countInversions(nums,mid,end);
    unsigned int mcount=merge(nums,begin,mid,end);

    return lcount+rcount+mcount;
}

int main(int argc,char** argv)
{
    vector<int> nums;
    ifstream input;
    if(argc>1)
	{
	    char *name=argv[1];
        input.open(name);//read from a txt file
	}
    if(input.is_open())
    {
        int num=0;
        while(input>>num)
            nums.push_back(num);
    }

    cout<<countInversions(nums,0,nums.size())<<endl;
    return 0;
}

Question 1
Download the text file here. (Right click and save link as)
This file contains all of the 100,000 integers between 1 and 100,000 (inclusive) in some order, with no integer repeated.

Your task is to compute the number of inversions in the file given, where the ith row of the file indicates the ith entry of an array.
Because of the large size of this array, you should implement the fast divide-and-conquer algorithm covered in the video lectures. The numeric answer for the given input file should be typed in the space below.
So if your answer is 1198233847, then just type 1198233847 in the space provided without any space / commas / any other punctuation marks. You can make up to 5 attempts, and we'll use the best one for grading.
(We do not require you to submit your code, so feel free to use any programming language you want --- just type the final numeric answer in the following space.)

[TIP: before submitting, first test the correctness of your program on some small test files or your own devising. Then post your best test cases to the discussion forums to help your fellow students!]