Programa en C# para contar inversiones en una array | 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
using System;
using System.Collections.Generic;
  
class GFG 
{
    static int[] arr = 
           new int[] {1, 20, 6, 4, 5};
  
    static int getInvCount(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
    public static void Main()
    {
        Console.WriteLine("Number of " + 
                          "inversions are " + 
                           getInvCount(arr.Length));
    }
}
// This code is contributed by Sam007

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 se deben agregar, se debe agregar el número de inversiones en el subarreglo izquierdo, el subarreglo derecho y fusionar().

¿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# implementation of counting the
// inversion using merge sort
using System;
public class Test 
{
    /* This method sorts the input array and 
       returns the number of inversions in 
       the array */
    static int mergeSort(int[] arr, 
                         int array_size)
    {
        int[] temp = new int[array_size];
        return _mergeSort(arr, temp, 0, 
                          array_size - 1);
    }
  
    /* An auxiliary recursive method that sorts 
       the input array and returns the number 
       of inversions in the array. */
    static 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 method merges two sorted arrays 
       and returns inversion count in the 
       arrays.*/
    static 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
    public static void Main()
    {
        int[] arr = 
              new int[] {1, 20, 6, 4, 5};
        Console.Write("Number of inversions are " + 
                       mergeSort(arr, 5));
    }
}
// This code is contributed by Rajput-Ji

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.