Friday, May 9, 2014

Number of inversions in an array

Problem: Find the number of pairs (i, j) of an array A indices with i < j and A[i] > A[j].

Solution:

unsigned long countSplitInversions(int *arr, unsigned long mid, unsigned long len)
{
vector<int> tempVect(arr, arr + mid);
unsigned long count = 0;
unsigned long i = 0, j = mid, k = 0;
for(; i < mid && j < len;)
{
if(arr[j] < tempVect[i])
{
arr[k++] = arr[j++];
count += (mid - i);
}
else
{
arr[k++] = tempVect[i++];
}
}
if(j < len)
{
while(j < len)
arr[k++] = arr[j++];
}
else if(i < mid)
{
while(i < mid)
arr[k++] = tempVect[i++];
}
return count;
}

unsigned long countInversions(int *arr, unsigned long len)
{
if(len == 1)
return 0;
unsigned long mid = len/2;
unsigned long leftInversions = countInversions(arr, mid);
unsigned long rightInversions = countInversions(arr + mid, len - mid);
unsigned long splitInversions = countSplitInversions(arr, mid, len);
return leftInversions + rightInversions + splitInversions;
}

No comments:

Post a Comment