Count Inversion in an Array using C++

The inversions of an array show; how many shifts/turns are needed to turn the array into its sorted form.
Inversion Count for an array points out how nearest the array is from being sorted. If an array is already in sorted form, then count inversion 0. Count inversion shall be maximum if the sorted array is in reverse order.

In simple words, we can say; how many changes are required to set the array into its sorted structure.

 Array Count Inversion in C++

Now we look at a simple code example to find count inversion of a given array.

// Program In C++ For count Inversion in an Array

#include<iostream> 
using namespace std;
int countInversion(int array[], int n) 
{ 
    int Count_Inversion = 0; 
    for (int i = 0; i < n - 1; i++) 
    {
    
        for (int j = i + 1; j < n; j++) 
        {
        
            if (array[i] > array[j])
			{
			 
                Count_Inversion++; 
              }
          }
    }
     return Count_Inversion; 
} 
  

int main() 
{ 
    int array[] = { 7, 5, 3, 2 };                             //initializing array
    int num = sizeof(array) / sizeof(array[0]);                 // getting size of array
    cout << "inversions are "<< countInversion(array, num);          //calling Fun
    return 0; 
}

inversions are: 6

Time Complexity: O(n^2)

Code Explanation

Every program in C++  starts execution from the main method. First of all, we initialize an array of type int with values 7,5,3,2. To getting the size of an array, we declare and initialize a variable num which stores the size of the array as shown in the code.

Then we call a function name countInversion(array,num). which takes two augments, one is the array (array) and second is the size of the array (num).

In countInversion() function, we initialize a variable Count_Inversion=0. After that, we implement nested “for loop”. Inside of inner loop, we applied the if condition as if (array[i] > array[j]). If the condition is true, then there is an increment in Count_Inversion. The same process is repeated until the condition in Outer most for loops gets false and the function will return Count_Inversion. Then the program will show the count_Inversion on the console window.

Related Articles