Programa Php 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 (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:

<?php 
// PHP program to Count Inversions
// in an array
function getInvCount(&$arr, $n)
{
    $inv_count = 0;
    for ($i = 0; $i < $n - 1; $i++)
        for ($j = $i + 1; $j < $n; $j++)
            if ($arr[$i] > $arr[$j])
                $inv_count++;
  
    return $inv_count;
}
  
// Driver Code
$arr = array(1, 20, 6, 4, 5 );
$n = sizeof($arr);
echo "Number of inversions are ", 
           getInvCount($arr, $n);
// This code is contributed by ita_c
?>

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.

Consulte el artículo completo sobre Contar inversiones en una array | ¡ Establezca 1 (usando Merge Sort) para obtener más detalles!