CODEWITHSUNDEEP
c++mergesort
Code Monkey
Code Monkey

Reputation: 9

Inversion counting giving trouble (implementation of modified merge sort)

Given this question:

Given an array A on size N, you need to find the number of ordered pairs (i, j) such that i < j and A[i] > A[j]

Input: First line contains one integer, N, size of array. Second line contains N space separated integers denoting the elements of the array A.

Output: Print the number of ordered pairs (i, j) such that i < j and A[i] > A[j].

Constraints:

1 ≤ N ≤ 10^6
1 ≤ A[i] ≤ 10^6

Source: hackerearth's merge sort tutorial

I'm encountering problems properly implementing the solution.

This is the code I wrote:

#include <iostream>

using namespace std;

int ar[10000000];
long long counting=0;

void merge(int* ALR, int* L, int left_length, int* R, int right_length) {
    int l = 0;
    int r = 0;
    for (int i = 0; i < left_length + right_length;) {

        if (l == left_length)ALR[i++] = R[r++];
        else if (r == right_length)ALR[i++] = L[l++];
        else if(L[l]>R[r]){
            counting+=(left_length-l);
            ALR[i++]=L[l++];
        }
        else    ALR[i++]=R[r++];

    }
}

void merge_sort(int* ALR, int length) {

    if (length == 1)return;

    int mid = length / 2;

    int* L = new int[mid];
    int* R = new int[length - mid];

    int k = 0;

    for (size_t i = 0; k < mid; i++)L[i] = ALR[k++];
    for (size_t i = 0; k < length; i++)R[i] = ALR[k++];

    merge_sort(L, mid);
    merge_sort(R, length - mid);

    merge(ALR, L, mid, R, length - mid);

    delete(L);
    delete(R);
}
int main() {

     int t;
     cin>> t;

     for(int i=0;i<t;i++)cin>> ar[i];

    merge_sort(ar, t);

  cout<<counting;

 return 0;

}

Now the problem is that I'm getting a wrong answer in the 2nd test case ...

The answer should be: 250194527312

The answer I get: 250002372570

Where did it go wrong?

Upvotes: 0

Views: 112

Answers (1)

Kenny Ostrom
Kenny Ostrom

Reputation: 5871

A general principle you should follow is unit testing small bits of code. In this case, you should test the merge function, to see if what you get when you merges is correct. If you had written a test which merges two very small arrays, then you would have seen the result be in descending order, and the inversion count would usually be wrong.

Here's the test case I used for merge-sort inversion counting:

// expect 3 inversions in [1,3,5,2,4,6]

Your actual problem is an easy error to make (flip the comparitor and count the other branch as an inversion), and I guarantee many experienced programmers would make some equivalent mistake before running their tests. The difference between a novice and veteran is knowing how to find those mistakes (and structure tests so that they are found automatically).

Upvotes: 1

Related Questions