Write a program to find the inversion count of an array.

Write a program to find the inversion count of an array.

Inversion Count for an array indicates – how far (or close) the array is from being sorted. If the array is already sorted then inversion count is 0. If the array is sorted in reverse order that inversion count is the maximum.

Formally speaking, two elements a[i] and a[j] form an inversion if a[i] > a[j] and i < j

Example:

The sequence 2, 4, 1, 3, 5 has three inversions (2, 1), (4, 1), (4, 3).

Input Format:

Input consists of n+1 integers where n corresponds to the number of elements in the array.

The first integer corresponds to n and the next n integers correspond to the elements in the array. Assume that the maximum number of elements in the array is 20.

Output Format:

The output consists of a single integer which corresponds to the number of inversions in an array.

Refer sample input and output for formatting specifications.

[All text in bold corresponds to the input and the rest corresponds to output.]

Sample Input and Output :

Enter the number of elements in the array

5

Enter the elements in the array

2

4

1

3

5

The inversion count of the array is 3

Program Code:

#include <stdio.h>

// Function to find Inversion count of the given array

int findInversionCount(int arr[], int n)

{

int inversionCount = 0,i,j;

for (i = 0; i < n - 1; i++)

{

for (j = i + 1; j < n; j++)

if (arr[i] > arr[j])

inversionCount++;

}

return inversionCount;

}

// main function

int main()

{

int n,arr[100],i;

 printf("Enter the number of elements in the array\n");

scanf("%d",&n);

printf("Enter the elements in the array\n");

for(i=0;i<n;i++){

scanf("%d",&arr[i]);

}

printf("The inversion count of the array is %d", findInversionCount(arr, n));

return 0;

}