Contando inversiones usando Set en C++ STL

El conteo de inversión para una array indica qué tan lejos (o cerca) está la array de ser ordenada. Si la array ya está ordenada, el recuento de inversión es 0. Si la array se ordena en orden inverso, el recuento de inversión es el 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).     

Ya hemos discutido a continuación los enfoques.
1) Enfoques basados ​​en Naive y Merge Sort.
2) Enfoque basado en árboles AVL.

En esta publicación, se analiza una implementación fácil del enfoque 2 usando Set en C++ STL .

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;
}

Producción:

Number of inversions count are : 6

Tenga en cuenta que la complejidad de tiempo en el peor de los casos de la implementación anterior es O(n ² ) ya que la función de distancia en STL toma O(n) tiempo en el peor de los casos, pero esta implementación es mucho más simple que otras implementaciones y tomaría mucho menos tiempo que el método Naive en promedio .

Este artículo es una contribución de Abhiraj Smit . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.