Counting Inversion [Merge sort]

Question

I am getting a wrong answer from the following procedure in my attempt to count inversions from a very large dataset.

I have also tried a few of other codes that have been given/suggested on the related posts and did try a lot of manipulations in my code itself [to get answer right] but got rejected. Provided that I don't know the right answer, I can just only verify if I have one.

Also, In order to help myself more, I tried it with O(n^2) way in order to get an answer right at least but the answer I got was rejected.

Code producing wrong output: -1887062008

#include <iostream>
#include <vector>
#include <fstream>

using namespace std;


int mergeAndCount(vector<int> & arr, int first, int second, int last) {

    vector<int> temp; 
    int i = first, j = second;
    int invCount = 0;

    while( i < second && j <= last ) {

        if( arr[i] > arr[j] ) {

            invCount += second - i; 
            temp.push_back( arr[j] );
            j++;
        }
        else {
            temp.push_back( arr[i] );
            i++;
        }
    }

    while( i < second ) {
        temp.push_back( arr[i++] );
    }

    while ( j <= last ) {
        temp.push_back( arr[j++] );
    }

    copy( temp.begin(), temp.end(), arr.begin()+first);

    return invCount;
}


int sortAndCount( vector<int>& arr, int low, int high ) {

    if( low >= high )
        return 0;

    int mid = low + (high-low)/2;
    int lic = sortAndCount( arr, low, mid );
    int ric = sortAndCount( arr, mid+1, high);
    int ic = mergeAndCount( arr, low, mid+1, high);

    return lic+ric+ic;
}


int getInversionCount(vector<int>& arr ) {
    if( arr.size() > 0 )
        return sortAndCount( arr, 0, arr.size()-1 );

    return 0;
}

void Test1() {

    vector<int> arr;

    ifstream inFile;

    inFile.open("w2.txt");

    if (!inFile) {
        cout << "Unable to open file datafile.txt"; 
    }

    int value;

    while(inFile >> value) {
        arr.push_back(value);
    }

    cout << getInversionCount( arr) << endl;
}


int main() {
    Test1();
    return 0;
}

Please read https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice — Ed Heal, Dec 15 '17 at 22:41
`cout << "Unable to open file datafile.txt";` -> Surely after this you should terminate the program?! — Ed Heal, Dec 15 '17 at 22:43
What was your input? What was the expected answer? What answer did you get? — user3386109, Dec 15 '17 at 22:52
Input is very large so I didn't post it here. I don't know the correct answer. According to above code, it's 23510 which is wrong. — , Dec 15 '17 at 22:54
Hmm, well it's always best to start with a small data set where you know what the right answer is supposed to be. Either that, or you need to tell us exactly how *"inversion"* is defined. Looking at the code, I'd say that the `k` loop isn't right. For one thing it assumes that `input1` and `input2` are the same size, which is not true if `big.size()` is an odd number. — user3386109, Dec 15 '17 at 22:59
Yes, I did try that but nothing is being worked for me. As of now, I have reached a state in which I am just trying to get my answer accepted. I have tried alot of things just to get it right but I am failing every time. — , Dec 15 '17 at 23:06
And even if they are not equal, one will be big by 1 element and if we take any array and compare it with another it won't create a problem at all as the last element is not required anyway. — , Dec 15 '17 at 23:12
Now why I am being awarded a negative, seriously! I hope I didn't break any law in here. — , Dec 15 '17 at 23:14
Please comment the `for` loops. I think when you do this it will help us — Ed Heal, Dec 15 '17 at 23:41

score 0 · Answer 1 · edited May 24 '21 at 21:04

I'm just a student and I have to make the same algorithm , so don't trust me very much ; but I think that in sortAndCount you have to make a conditional for the number of elements. Like :

int sortAndCount( vector<int>& arr, int low, int high ) {

     if( air.size()==1){
         return 0;
    }
    else if( arr.size() >=2){
      int mid = low + (high-low)/2;
      int lic = sortAndCount( arr, low, mid );
      int ric = sortAndCount( arr, mid+1, high);
      int ic = mergeAndCount( arr, low, mid+1, high);
    }
     return lic+ric+ic;
 }

Counting Inversion [Merge sort]

1 Answers1