I am working on this code to count the number of inversion pairs in a given arra

Question

I am working on this code to count the number of inversion pairs in a given array,
my code is running fine, but the output value is wrong, it should give (12), but it keeps giving me 0, I could not figure out the problem? how can I fix it please ?

thanks,


#include<iostream>
using namespace std;

int merge(int arr[], int low,int mid,int high)
{
int c=0;
int p,q,index,k;
int a[8],b[8];
p=low;
index=low;
q=mid+1;


while((p<=mid)&&(q<=high))
{
if(a[p]<=a[q])
{
b[index]=a[p];
p++;
}
else
{
b[index]=a[q];
q++;
c = c + (mid-p+1);
}
index++;
}
if(p>mid)
{
for(k=q;k<=high;k++)
{
b[index]=a[k];
index++;
}
}

else
{
for(k=p;k<=mid;k++)
{
b[index]=a[k];
index++;
}
}
for(k=low;k<=high;k++)
a[k]=b[k];
return c;
}

int COUNT_INVERSIONS(int A[], int low, int high)
{
static int count =0;
int mid = (low + high)/2;
if (low < high)
{

count = count + COUNT_INVERSIONS(A, low, mid);
count = count + COUNT_INVERSIONS(A, low + 1, high );
count= count + merge(A, low, mid, high);
}
return count;
}
int main()
{
int arr[] = {10,2,30,4,50,6,7,8};
cout<<COUNT_INVERSIONS(arr,0,7)<<endl…
return 0;
}

Explanation / Answer

looked again, and realized that change didn't fix it :(

This code does what you want, but is based on a merge sort from here: http://www.geeksforgeeks.org/archives/3968, not your original code. Hopefully you can find what you need in here to get yours working right!

#include
using namespace std;

int MergeAndCount(int A[], int low, int mid, int high);
int MergeInvCount(int A[], int low, int high);
int BruteInvCount(int arr[], int n);

int main()
{
//int arr[] = {1, 4, 2, 3};
int arr[] = {10,2,30,4,50,6,7,8};
cout << "Brute Inversion Count [O(n^2)]: " << BruteInvCount(arr, 8) << endl;
cout << "Merge Inversion Count [O(n Log n)]: " << MergeInvCount(arr, 0, 7) << endl;
return 0;
}

int BruteInvCount(int arr[], int n)
{
int inv_count = 0;
int i, j;

for(i = 0; i < n - 1; i++)
for(j = i+1; j < n; j++)
if(arr[i] > arr[j])
inv_count++;

return inv_count;
}

int MergeInvCount(int arr[], int left, int right)
{
int mid, inv_count = 0;
if (right > left)
{
/* Divide the array into two parts and call _mergeSortAndCountInv()
for each of the parts */
mid = (right + left)/2;

/* Inversion count will be sum of inversions in left-part, right-part
and number of inversions in merging */
inv_count = MergeInvCount(arr, left, mid);
inv_count += MergeInvCount(arr, mid+1, right);

/*Merge the two parts*/
inv_count += MergeAndCount(arr, left, mid+1, right);
}
return inv_count;
}

/* This funt merges two sorted arrays and returns inversion count in
the arrays.*/
int MergeAndCount(int arr[], int left, int mid, int right)
{
int i, j, k;
int temp[8];
int inv_count = 0;

i = left; /* i is index for left subarray*/
j = mid; /* i is index for right subarray*/
k = left; /* i is index for resultant merged subarray*/
while ((i <= mid - 1) && (j <= right))
{
if (arr[i] <= arr[j])
{
temp[k++] = arr[i++];
}
else
{
temp[k++] = arr[j++];

/*this is tricky -- see above explanation/diagram for merge()*/
inv_count = inv_count + (mid - i);
}
}

/* Copy the remaining elements of left subarray
(if there are any) to temp*/
while (i <= mid - 1)
temp[k++] = arr[i++];

/* Copy the remaining elements of right subarray
(if there are any) to temp*/
while (j <= right)
temp[k++] = arr[j++];

/*Copy back the merged elements to original array*/
for (i=left; i <= right; i++)
arr[i] = temp[i];

return inv_count;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.