C++ program to count the inversions in the given array
Introduction
An inversion is formed between two elements a[i] and a[j], if a[i] > a[j] and i<j.
Let us assume a array
3 5 6 9 1 2 7 8
Possible inversion in the array are:
Inversions: 10
Explanation: (3,1), (3,2), (5,1), (5,2), (6,1), (6,2)
(9,1), (9,2), (9,7), (9,8)
Algorithm:
1. Compare the values of the element with each other.
2. Increment the counter if the value at lower index is higher.
3. Display the result.
2. Increment the counter if the value at lower index is higher.
3. Display the result.
Program:
#include<iostream>
using namespace std;
int CountInversion(int a[], int n)
{
int i, j, count = 0;
for(i = 0; i < n; i++)
{
for(j = i+1; j < n; j++)
if(a[i] > a[j])
count++;
}
return count;
}
int main()
{
int n, i;
cout<<"\nEnter the number of data elements: "<<endl;
cin>>n;
int arr[n];
cout<<"Enter elements : ";
for(i = 0; i < n; i++)
{
cin>>arr[i];
}
// Printing the number of inversion in the array.
cout<<"\nThe number of inversion in the array: "<<CountInversion(arr, n);
return 0;
}
Output:
Enter the number of data elements:
8
Enter elements : 3 5 6 9 1 2 7 8
The number of inversion in the array: 10
Comments