Programa Javascript 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:

<script>
// Javascript program to count inversions 
// in an array
arr = [1, 20, 6, 4, 5];
  
function getInvCount(arr)
{
    let inv_count = 0;
    for(let i = 0; i < arr.length - 1; i++)
    {
        for(let j = i + 1; j < arr.length; j++)
        {
            if(arr[i] > arr[j]) inv_count++;
        }
    }
    return inv_count;
}
  
// function call
document.write("Number of inversions are "+ 
                getInvCount(arr));
  
// This code is contributed by Karthik SP
</script>

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:

<script>
// Javascript program to implement
// the above approach
// Function to count the number of 
// inversions during the merge process
function mergeAndCount(arr, l, m, r)
{    
    // Left subarray
    let left = [];
          
    for(let i = l; i < m + 1; i++)
    {
        left.push(arr[i]); 
    }
          
    // Right subarray
    let right = [];
  
    for(let i = m + 1; i < r + 1; i++)
    {
        right.push(arr[i]);
    }
          
    let i = 0, j = 0, k = l, swaps = 0;
    while (i < left.length && 
           j < right.length)
    {
        if (left[i] <= right[j])
        {
            arr[k++] = left[i++];
        }
        else
        {
            arr[k++] = right[j++];
            swaps += (m + 1) - (l + i);
        }
    }
    while (i < left.length)
    {
        arr[k++] = left[i++];
    }
          
    while (j < right.length)
    {
        arr[k++] = right[j++];
    }
    return swaps;
}
      
// Merge sort function
function mergeSortAndCount(arr, l, r)
{        
    // Keeps track of the inversion count 
    // at a particular node of the recursion 
    //                             tree
    let count = 0;
      
    if (l < r) 
    {
        let m = Math.floor((l + r) / 2);
              
         // Total inversion count = left subarray 
         // count + right subarray count + merge count
              
         // Left subarray count
         count += mergeSortAndCount(arr, l, m);
              
         // Right subarray count
         count += mergeSortAndCount(arr, m + 1, r);
              
         // Merge count
         count += mergeAndCount(arr, l, m, r);
    }
    return count;
}
      
// Driver code
let arr = new Array(1, 20, 6, 4, 5 );
document.write(
mergeSortAndCount(
arr, 0, arr.length - 1));
      
// This code is contributed by avanitrachhadiya2155
</script>

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.