C++ program to count the inversions in the given array














































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.

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





More Articles of Shaik Aftab Ahmed:

Name Views Likes
C++ Program to Find the Frequency of Odd & Even Numbers in the given Matrix 239 1
C++ program to Sort a Linked List Using Merge Sort 225 1
C++ Program to Implement a Linked List representation of a Binary tree 221 1
C++ Program to Check for balanced parentheses in an expression 146 1
C++ Program to Perform Inorder, Preorder, Postorder traversals in a binary tree. 181 1
C++ program to print Indian flag 200 1
C++ program to Convert a multi level linked list to a singly linked list 151 1
C++ program to print right view of a Binary tree using queue 162 1
C++ Program to implement Huffman Coding Compression Algorithm 225 1
C++ Program to Create a Height Balanced Binary Tree 160 1
C++ program to implement Prims algorithm 234 1
C++ Program for BFS Traversal 173 1
C++ Progam to Evaluate a Prefix Expression 167 1
C++ Program to Implement Queue using Linked List 175 1
C++ implementation of Stack using Linked list 173 1
C++ program to find the intersection point of two linked lists 228 1
C++ program to count the inversions in the given array 215 1
C++ program to perform D.N.F sort 227 1
C++ program to print all possible subsets of a String 214 1
C++ program to count the number of ones in a binary representation of a number 229 1
C++ program to print all possible subsets of a set 246 1
C++ program to find the largest word in a String 220 1
C++ Program to print a matrix in Spiral order 228 1
C++ program to convert from Binary to Decimal, Octal to Decimal, Hexadecimal to Decimal 227 1
C limits library 254 1
Program to add two Binary numbers 231 1

Comments