Q2: Let A[n] be an array of n distinct integers. If i < j and A[i] > A[j], then the pair (i, j)

is called an inversion of A. Write a C/C++ program that determines the number of

inversions in any permutation on n elements in O(n lg n) worst-case time.

(Hint: Modify merge sort)

Example: A = {4, 1, 3, 2} output is 4

program:-

#include<stdio.h>

int total_inversions(int arr[], int n, int count);
int main(){
   int arr[] = {4, 1, 3, 2};
   int n = sizeof(arr) / sizeof(arr[0]);
   int count = 0;
   count = total_inversions(arr, n , count);
   printf("%d", count); return 0;
}
int total_inversions(int arr[], int n, int count){
   for(int i = 0; i < n-1; i++){
      for(int j = i+1; j < n; j++){
        if (arr[i] > arr[j]){ count++; }
      }
   }
   return count;
}

aryangupta001

Posts (2)