Question

Fix the C++ code to count the number of inversions using the given array.
The answer is 8 inversions, but I am only getting 6 inversions.

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <iostream>
using namespace std;

int mergeInversion(int arr[], int l, int m, int r)
{
    // size of the two arrays
    int n1 = m - l + 1;
    int n2 = r - m;

    // create temporary arrays
    int L[n1];
    int R[n2];

    // Copy the data over into the temp arrays
    for(int i = 0; i < n1; ++i)
    {
        L[i] = arr[l+i];
    }
    for(int j = 0; j < n2; ++j)
    {
        R[j] = arr[m + 1 + j];
    }

    // Counting the inversions.
    int counter = 0;
    for(int i = 0; i < n1; i++)
    {
        for(int j = 0; j < n2; j++)
        {
            if(L[i] > R[i]) // check if its an inversion
            {
                counter++;
            }
        }
    }
    return counter;
}

// Divide-and-Conquer for inversions
int countInversions(int arr[], int l, int r)
{
    int countIs = 0;

    if(l < r)
    {
        // find middle pt
        int m = (l+r)/2;

        // sort the first half and last half
        countIs = countIs + countInversions(arr, l, m);     // first half sub-array doing inversion recursively
        countIs = countIs + countInversions(arr, m+1, r);   // last half sub-array doing inversion recursively

        // now conquer by merging the sub-arrays!
        countIs = countIs + mergeInversion(arr, l, m, r);   // count the inversions in both arrays
    }
    return countIs;
}

// driver
int main()
{
    // part(c) using the input a = [2, 6, 1, 5, 4, 3]
    int a[] = {2, 6, 1, 5, 4, 3};

    // array size
    int n = sizeof(a)/sizeof(*a);

    cout << "\nTotal # of Inversions: " << countInversions(a, 0, n-1);

    return 0;
}

Answer 1

#include <bits/stdc++.h>
using namespace std;

int mergeInversion(int arr[], int l, int m, int r)
{
// size of the two arrays
int n1 = m - l + 1;
int n2 = r - m;

// create temporary arrays
int L[n1];
int R[n2];

// Copy the data over into the temp arrays
for(int i = 0; i < n1; ++i)
{
L[i] = arr[l+i];
}
for(int j = 0; j < n2; ++j)
{
R[j] = arr[m + 1 + j];
}
int i=0,j=0,k=l,count=0;
// i and j are index of left and right arrays during merging
//during merging if L[i] is greater than R[j], then there are (n1 – i) inversions. because left and right subarrays are sorted,
//so all the remaining elements in left-subarray (L[i+1], L[i+2] … L[mid]) will be greater than R[j]
  
while(i<n1 && j<n2){
if(L[i]<=R[j])
arr[k++] = L[i++];
else{
arr[k++] = R[j++];
count += n1-i;
}
}
while(i<n1)
arr[k++] = L[i++];
while(j<n2)
arr[k++] = R[j++];
return count;
  

}

// Divide-and-Conquer for inversions
int countInversions(int arr[], int l, int r)
{
int countIs = 0;

if(l < r)
{
// find middle pt
int m = (l+r)/2;

// sort the first half and last half
countIs = countIs + countInversions(arr, l, m); // first half sub-array doing inversion recursively
countIs = countIs + countInversions(arr, m+1, r); // last half sub-array doing inversion recursively

// now conquer by merging the sub-arrays!
countIs = countIs + mergeInversion(arr, l, m, r); // count the inversions in both arrays
}
return countIs;
}

// driver
int main()
{
// part(c) using the input a = [2, 6, 1, 5, 4, 3]
int a[] = {2, 4, 1, 3, 5};

// array size
int n = sizeof(a)/sizeof(*a);

cout << "\nTotal # of Inversions: " << countInversions(a, 0, n-1);

return 0;
}