por - Conservar el orden de las teclas(clasificación estable) al ordenar con uasort de PHP

sort array php

Question

Esta pregunta está realmente inspirada en otra aquí en SO y quería expandirla un poco.

Tener una matriz asociativa en PHP es posible ordenar sus valores, pero donde los valores son iguales para preservar el orden de la clave original, usando una (o más) de las funciones de clasificación incorporadas de PHP.

Aquí hay un script que usé para probar posibles soluciones (no he encontrado ninguno):

<?php
header(''Content-type: text/plain'');
for($i=0;$i<10;$i++){
    $arr[''key-''.$i] = rand(1,5)*10;
}
uasort($arr, function($a, $b){
    // sort condition may go here //
    // Tried: return ($a == $b)?1:($a - $b); //
    // Tried: return $a >= $b; //
});
print_r($arr);
?>

Peligro : Debido a que las claves se ordenan en la matriz original, no se sienta tentado a sugerir ninguna clasificación por clave para restaurar el orden original. Hice el ejemplo con ellos ordenado para que sea más fácil verificar visualmente su orden en la salida.

Answer 1

Esta es una solución con la que puede lograr una clasificación estable en la función de usort.

public function sortBy(array &$array, $value_compare_func)
{
    $index = 0;
    foreach ($array as &$item) {
        $item = array($index++, $item);
    }
    $result = usort($array, function($a, $b) use ($value_compare_func) {
        $result = call_user_func($value_compare_func, $a[1], $b[1]);
        return $result == 0 ? $a[0] - $b[0] : $result;
    });
    foreach ($array as &$item) {
        $item = $item[1];
    }
    return $result;
}

Answer 2

Para completar, también debes ver la transformación de Schwartz :

// decorate step
$key = 0;
foreach ($arr as &$item) {
        $item = array($item, $key++); // add array index as secondary sort key
}

// sort step
asort($arr); // sort it

// undecorate step
foreach ($arr as &$item) {
    $item = $item[0]; // remove decoration from previous step
}

El algoritmo de ordenación predeterminado de PHP funciona bien con matrices, debido a esto:

array(1, 0) < array(2, 0); // true
array(1, 1) < array(1, 2); // true

Si desea usar sus propios criterios de clasificación, también puede usar uasort() :

// each parameter is an array with two elements
// [0] - the original item
// [1] - the array key
function mysort($a, $b)
{
    if ($a[0] != $b[0]) {
        return $a[0] < $b[0] ? -1 : 1;
    } else {
        // $a[0] == $b[0], sort on key
        return $a[1] < $b[1] ? -1 : 1; // ASC
    }
}

Answer 3

Para referencia futura, he puesto un conjunto de variantes de clasificación estables de funciones PHP integradas en Github: https://github.com/vanderlee/PHP-stable-sort-functions , basadas en la solución de @Jack y algunos otros trucos.

Answer 4

Solo para completar las respuestas con un caso muy específico. Si las teclas de array de $array son las predeterminadas, basta con un simple array_values(asort($array)) (aquí, por ejemplo, en orden ascendente)

Answer 5

array_multisort es útil, solo use un rango ordenado como segunda matriz ( $order es solo temporal, sirve para ordenar los elementos equivalentes de la primera matriz en su orden original):

$a = [
  "key-0" => 5,
  "key-99" => 3,
  "key-2" => 3,
  "key-3" => 7
];

$order = range(1,count($a));
array_multisort($a, SORT_ASC, $order, SORT_ASC);

var_dump($a);

Salida

array(4) {
  ["key-99"]=>
  int(3)
  ["key-2"]=>
  int(3)
  ["key-0"]=>
  int(5)
  ["key-3"]=>
  int(7)
}

Utilicé datos de prueba con claves no ordenadas para demostrar que funciona correctamente. No obstante, aquí está el resultado de su script de prueba:

Array
(
    [key-1] => 10
    [key-4] => 10
    [key-5] => 20
    [key-8] => 20
    [key-6] => 30
    [key-9] => 30
    [key-2] => 40
    [key-0] => 50
    [key-3] => 50
    [key-7] => 50
)

Abajo

Solo funciona con comparaciones predefinidas, no puede usar su propia función de comparación. Los valores posibles (segundo parámetro de array_multisort() ) son:

Banderas de tipo de ordenamiento :

• SORT_ASC - ordena los elementos en orden ascendente.
• SORT_DESC - ordenar los elementos de forma descendente.
• SORT_REGULAR : compare los elementos normalmente (no cambie los tipos)
• SORT_NUMERIC - comparar elementos numéricamente
• SORT_STRING - compara elementos como cadenas
• SORT_LOCALE_STRING : compara elementos como cadenas, según la configuración regional actual. Utiliza la configuración regional, que se puede cambiar utilizando setlocale()
• SORT_NATURAL : compare elementos como cadenas usando "ordenamiento natural" como natsort()
• SORT_FLAG_CASE - se puede combinar (OR a nivel de bit) con SORT_STRING o SORT_NATURAL para ordenar cadenas sin distinción de mayúsculas y minúsculas

Answer 6

Como PHP no es compatible con el ordenamiento estable después de PHP 4.1.0 , debe escribir su propia función.

Esto parece hacer lo que estás preguntando: http://www.php.net/manual/en/function.usort.php#38827

Como dice el manual, "si dos miembros se comparan como iguales, su orden en el conjunto ordenado no está definido". Esto significa que el tipo utilizado no es "estable" y puede cambiar el orden de los elementos que se comparan por igual.

A veces realmente necesitas un tipo estable. Por ejemplo, si ordena una lista por un campo, luego ordene nuevamente por otro campo, pero no quiere perder el orden del campo anterior. En ese caso, es mejor usar usort con una función de comparación que tenga en cuenta ambos campos, pero si no puede hacerlo, utilice la función siguiente. Es un tipo de fusión, que tiene una complejidad O (n * log (n)) garantizada, lo que significa que se mantiene razonablemente rápido incluso cuando se usan listas más grandes (a diferencia de bubblesort y ordenamiento de inserción, que son O (n ^ 2)).

<?php
function mergesort(&$array, $cmp_function = ''strcmp'') {
    // Arrays of size < 2 require no action.
    if (count($array) < 2) return;
    // Split the array in half
    $halfway = count($array) / 2;
    $array1 = array_slice($array, 0, $halfway);
    $array2 = array_slice($array, $halfway);
    // Recurse to sort the two halves
    mergesort($array1, $cmp_function);
    mergesort($array2, $cmp_function);
    // If all of $array1 is <= all of $array2, just append them.
    if (call_user_func($cmp_function, end($array1), $array2[0]) < 1) {
        $array = array_merge($array1, $array2);
        return;
    }
    // Merge the two sorted arrays into a single sorted array
    $array = array();
    $ptr1 = $ptr2 = 0;
    while ($ptr1 < count($array1) && $ptr2 < count($array2)) {
        if (call_user_func($cmp_function, $array1[$ptr1], $array2[$ptr2]) < 1) {
            $array[] = $array1[$ptr1++];
        }
        else {
            $array[] = $array2[$ptr2++];
        }
    }
    // Merge the remainder
    while ($ptr1 < count($array1)) $array[] = $array1[$ptr1++];
    while ($ptr2 < count($array2)) $array[] = $array2[$ptr2++];
    return;
}
?>

Además, puede encontrar este hilo del foro interesante.