Example: the list [41, 72, 3, 74, 31] has 5 inversions, namely (41, 3),(41, 31),

Question

Example: the list [41, 72, 3, 74, 31] has 5 inversions, namely (41, 3),(41, 31),(72, 3),(72, 31),(74, 31).

Design a O(n log n) divide and conquer algorithm to count the number of inversions of a list of length n with distinct integers.

(Hint: alter mergesort and keep count of the inversions during the merge part.)

3. Given a list of distinct integers a 1...nl, an inversion is a pair of elements a il. ail such that a[i] a[J] and i j. Example: the list [41, 72,3,74,31] has 5 inversions, namely (41, 3), (41,31), (72,3), (72,31), (74,31). Design a O(nlog n) divide and conquer algorithm to count the number of inversions of a list of length n with distinct integers. ( Hint: alter mergesort and keep count of the inversions during the merge part. .)

Explanation / Answer

// C++ code count inversions in array
// Time Complexity: O(nlogn)

#include <iostream>
#include <iomanip>
#include <fstream>
#include <vector>
#include <stdlib.h>   
#include <math.h>

using namespace std;

// merge two array
int merge(int inputArray[], int temporary[], int begin, int m, int end)
{
int i = begin, j = m, k = begin, totalInversions = 0;

while ((i <= m - 1) && (j <= end))
{
      if (inputArray[i] <= inputArray[j])
      {
        temporary[k++] = inputArray[i++];
      }
      else
      {
      temporary[k++] = inputArray[j++];

      // inversions found through the rray
      totalInversions = totalInversions + (m - i);
      }
}
while (i <= m - 1)
    temporary[k++] = inputArray[i++];

while (j <= end)
    temporary[k++] = inputArray[j++];
for (i=begin; i <= end; i++)
    inputArray[i] = temporary[i];

return totalInversions;
}

// sort input array
int merge_sortArray(int array[], int temporary[], int begin, int end)
{
int m, totalInversions = 0;
if (end > begin)
{
    m = (end + begin)/2;

    // count inversions in subarrays
    totalInversions = merge_sortArray(array, temporary, begin, m);
    totalInversions = totalInversions + merge_sortArray(array, temporary, m+1, end);

    totalInversions = totalInversions + merge(array, temporary, begin, m+1, end);
}
return totalInversions;
}

int mergeSort(int array[], int size)
{
int *temporary = (int *)malloc(sizeof(int)*size);
return merge_sortArray(array, temporary, 0, size - 1);
}

int main()
{
int size;
cout << "Enter size of array: ";
cin >> size;

int array[size];

for (int i = 0; i < size; ++i)
{
     cout << "Enter array[" << (i+1) << "]: ";
     cin >> array[i];
}

cout << " Total inversions in array: " << mergeSort(array, size) << endl;

return 0;
}

/*
output:

Enter size of array: 5
Enter array[1]: 1
Enter array[2]: 20
Enter array[3]: 6
Enter array[4]: 4
Enter array[5]: 5

Total inversions in array: 5

*/

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

---

---

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