programa en C para contar inversiones en un arreglo | Conjunto 1 (usando la ordenación por combinación)

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 <stdio.h>
#include <stdlib.h>
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]);
    printf(" Number of inversions are %d \n",
           getInvCount(arr, n));
    return 0;
}

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 <stdio.h>
#include <stdlib.h>
 
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 = (int*)malloc(sizeof(int) *
                             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 the 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 function 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 argv, char** args)
{
    int arr[] = {1, 20, 6, 4, 5};
    printf("Number of inversions are %d \n",
            mergeSort(arr, 5));
    getchar();
    return 0;
}

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.