A contagem de inversão para uma matriz indica - a que distância (ou perto) a matriz está de ser classificada. Se a matriz já estiver classificada, a contagem de inversão será 0. Se a matriz for classificada na ordem reversa, a contagem de inversão será o máximo.

    Two elements a[i] and a[j] form an inversion if 
     a[i] > a[j] and i < j. For simplicity, we may 
     assume that all elements are unique.

     Example:
     Input:  arr[] = {8, 4, 2, 1}
     Output: 6
     Given array has six inversions (8,4), (4,2),
     (8,2), (8,1), (4,1), (2,1).     

Já discutimos as abordagens abaixo.
1) Abordagens baseadas na classificação ingênua e mesclada.
2) Abordagem baseada em árvore AVL.

Neste post, uma implementação fácil da abordagem 2 usando Set in C++ STL é discutida.

1) Create an empty Set in C++ STL (Note that a Set in C++ STL is 
   implemented using Self-Balancing Binary Search Tree). And insert
   first element of array into the set.

2) Initialize inversion count as 0.

3) Iterate from 1 to n-1 and do following for every element in arr[i]
     a) Insert arr[i] into the set.
     b) Find the first element greater than arr[i] in set
        using upper_bound() defined Set STL.
     c) Find distance of above found element from last element in set
        and add this distance to inversion count.

4) Return inversion count.

// A STL Set based approach for inversion count 
#include<bits/stdc++.h>
using namespace std;
  
// Returns inversion count in arr[0..n-1]
int getInvCount(int arr[],int n)
{
    // Create an empty set and insert first element in it
    multiset<int> set1;
    set1.insert(arr[0]);
  
    int invcount = 0; // Initialize result
  
    multiset<int>::iterator itset1; // Iterator for the set
  
    // Traverse all elements starting from second
    for (int i=1; i<n; i++)
    {
        // Insert arr[i] in set (Note that set maintains
        // sorted order)
        set1.insert(arr[i]);
  
        // Set the iterator to first greater element than arr[i]
        // in set (Note that set stores arr[0],.., arr[i-1]
        itset1 = set1.upper_bound(arr[i]);
  
        // Get distance of first greater element from end
        // and this distance is count of greater elements
        // on left side of arr[i]
        invcount += distance(itset1, set1.end());
    }
  
    return invcount;
}
  
// Driver program to test above
int main()
{
    int arr[] = {8, 4, 2, 1};
    int n = sizeof(arr)/sizeof(int);
    cout << "Number of inversions count are : "
         << getInvCount(arr,n);
    return 0;
}

Saída:

Number of inversions count are : 6

Observe que o pior caso de complexidade de tempo da implementação acima é O (n ² ), pois a função de distância em STL leva O (n) tempo de pior caso, mas esta implementação é muito mais simples do que outras implementações e levaria muito menos tempo do que o método Naive em média .

Este artigo é uma contribuição de Abhiraj Smit . Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima