Programa C++ para contar inversiones en una array: conjunto 1 (usando Merge Sort)

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, entonces el conteo de inversión es 0, pero si la array está ordenada en orden inverso, el conteo de inversión es el máximo. 
Hablando formalmente, dos elementos a[i] y a[j] forman una inversión si a[i] > a[j] e i < j 
Ejemplo: 

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

Input: arr[] = {3, 1, 2}
Output: 2
Explanation: Given array has two inversions:
(3, 1), (3, 2) 

MÉTODO 1 (Simple):  

Enfoque: recorra la array y, para cada índice, encuentre la cantidad de elementos más pequeños en su lado derecho de la array. Esto se puede hacer usando un bucle anidado. Sume los recuentos de todos los índices de la array e imprima la suma.

Algoritmo:

1. Atraviesa la array de principio a fin
2. Para cada elemento, encuentre el recuento de elementos más pequeños que el número actual hasta ese índice usando otro ciclo.
3. Suma el recuento de inversión para cada índice.
4. Imprime el conteo de inversiones.

Implementación:

// C++ program to Count Inversions
// in an array
#include <bits/stdc++.h>
using namespace std;
  
int getInvCount(int arr[], int n)
{
    int inv_count = 0;
    for (int i = 0; i < n - 1; i++)
        for (int j = i + 1; j < n; j++)
            if (arr[i] > arr[j])
                inv_count++;
  
    return inv_count;
}
  
// Driver Code
int main()
{
    int arr[] = {1, 20, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << " Number of inversions are " << 
              getInvCount(arr, n);
    return 0;
}
// This code is contributed by Akanksha Rai

Producción:

 Number of inversions are 5

Análisis de Complejidad: 

• Complejidad de tiempo: O (n ^ 2), se necesitan dos bucles anidados para atravesar la array de principio a fin, por lo que la complejidad de tiempo es O (n ^ 2)
• Complejidad espacial : O(1), No se requiere espacio adicional.

MÉTODO 2 (mejorar clasificación por fusión): 

Enfoque: 
suponga el número de inversiones en la mitad izquierda y la mitad derecha de la array (sea inv1 e inv2); ¿Qué tipos de inversiones no se tienen en cuenta en Inv1 + Inv2? La respuesta es: las inversiones que deben contarse durante el paso de fusión. Por lo tanto, para obtener el número total de inversiones que deben agregarse, se debe agregar el número de inversiones en el subarreglo izquierdo, el subarreglo derecho y merge().

¿Cómo obtener el número de inversiones en merge()?  
En el proceso de fusión, let i se usa para indexar el subconjunto izquierdo y j para el subconjunto derecho. En cualquier paso de merge(), si a[i] es mayor que a[j], entonces hay inversiones (mid – i). porque los subarreglos izquierdo y derecho están ordenados, por lo que todos los elementos restantes en el subarreglo izquierdo (a[i+1], a[i+2] … a[mid]) serán mayores que a[j]

La imagen completa:

Algoritmo: 

1. La idea es similar a la ordenación por fusión, divida la array en dos mitades iguales o casi iguales en cada paso hasta llegar al caso base.
2. Cree una combinación de funciones que cuente el número de inversiones cuando se fusionan dos mitades de la array, cree dos índices i y j, i es el índice de la primera mitad y j es un índice de la segunda mitad. si a[i] es mayor que a[j], entonces hay inversiones (mid – i). porque los subarreglos izquierdo y derecho están ordenados, por lo que todos los elementos restantes en el subarreglo izquierdo (a[i+1], a[i+2] … a[mid]) serán mayores que a[j].
3. Cree una función recursiva para dividir la array en mitades y encuentre la respuesta sumando el número de inversiones en la primera mitad, el número de inversiones en la segunda mitad y el número de inversiones fusionando los dos.
4. El caso base de recursividad es cuando solo hay un elemento en la mitad dada.
5. Imprime la respuesta

Implementación:

// C++ program to Count Inversions in 
// an array using Merge Sort
#include <bits/stdc++.h>
using namespace std;
  
int _mergeSort(int arr[], int temp[], 
               int left, int right);
int merge(int arr[], int temp[], 
          int left, int mid, int right);
  
/* This function sorts the input 
   array and returns the number 
   of inversions in the array */
int mergeSort(int arr[], int array_size)
{
    int temp[array_size];
    return _mergeSort(arr, temp, 0, 
                      array_size - 1);
}
  
/* An auxiliary recursive function that 
   sorts the input array and returns the 
   number of inversions in the array. */
int _mergeSort(int arr[], int temp[], 
               int left, int right)
{
    int mid, inv_count = 0;
    if (right > left) 
    {
        /* Divide the array into two parts and 
           call _mergeSortAndCountInv() for 
           each of the parts */
        mid = (right + left) / 2;
  
        /* Inversion count will be sum of inversions 
           in left-part, right-part and number of 
           inversions in merging */
        inv_count += _mergeSort(arr, temp, 
                                left, mid);
        inv_count += _mergeSort(arr, temp, 
                                mid + 1, right);
  
        // Merge the two parts
        inv_count += merge(arr, temp, 
                           left, mid + 1, right);
    }
    return inv_count;
}
  
/* This funt merges two sorted arrays and 
   returns inversion count in the arrays.*/
int merge(int arr[], int temp[], 
          int left, int mid, int right)
{
    int i, j, k;
    int inv_count = 0;
  
    // i is index for left subarray
    i = left;
  
    // j is index for right subarray 
    j = mid; 
  
    // k is index for resultant merged 
    // subarray
    k = left; 
  
    while ((i <= mid - 1) && 
           (j <= right)) 
    {
        if (arr[i] <= arr[j]) 
        {
            temp[k++] = arr[i++];
        }
        else 
        {
            temp[k++] = arr[j++];
  
            /* This is tricky -- see above 
               explanation/diagram for merge()*/
            inv_count = inv_count + (mid - i);
        }
    }
  
    /* Copy the remaining elements of left 
       subarray (if there are any) to temp*/
    while (i <= mid - 1)
        temp[k++] = arr[i++];
  
    /* Copy the remaining elements of right 
       subarray (if there are any) to temp*/
    while (j <= right)
        temp[k++] = arr[j++];
  
    /* Copy back the merged elements to 
       original array*/
    for (i = left; i <= right; i++)
        arr[i] = temp[i];
  
    return inv_count;
}
  
// Driver code
int main()
{
    int arr[] = {1, 20, 6, 4, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    int ans = mergeSort(arr, n);
    cout << " Number of inversions are " << ans;
    return 0;
}
  
// This is code is contributed by rathbhupendra

Producción:

Number of inversions are 5

Análisis de Complejidad:

• Complejidad de tiempo: O (n log n), el algoritmo utilizado es divide y vencerás, por lo que en cada nivel, se necesita un recorrido de array completo y hay niveles de log n, por lo que la complejidad de tiempo es O (n log n).
• Complejidad espacial : O(n), array temporal.

Tenga en cuenta que el código anterior modifica (u ordena) la array de entrada. Si queremos contar solo las inversiones, debemos crear una copia de la array original y llamar a mergeSort() en la copia para conservar el orden de la array original.