Préserver l'ordre des clés (tri stable) lors du tri avec PHP uasort

Cette question est en fait inspiré d'un autre ici et je voulais la développer un peu.

Avoir un tableau associatif en PHP il est possible de trier ses valeurs, mais où les valeurs sont égales à préserver la clé d'origine, en utilisant un (ou plusieurs) de PHP intégré dans la fonction de tri?

Voici un script que j'ai utilisé pour tester des solutions possibles (n'ai pas trouvé d'):

<?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);
?>

Piège: Parce que les touches sont classés dans le tableau d'origine, s'il vous plaît ne pas être tenté de suggérer le tri par clé pour restaurer l'ordre d'origine. J'ai fait l'exemple avec eux condamnée à être plus facile de vérifier visuellement leur ordre dans la sortie.

  • En d'autres termes, la solution à cette question est un stable algorithme de tri, qu'aucun de PHP sur les algorithmes de tri sont, soi-disant.
  • Je me doutais bien que beaucoup, mais je voudrais une réponse définitive et/ou une solution de contournement possible.
  • Est-il une raison pour utiliser biult fonctions seulement ?
  • php.net/manual/en/array.sorting.php - Si l'une de ces fonctions de tri, évalue deux membres de l'égalité, l'ordre n'est pas défini (le tri n'est pas stable).
  • Tout d'abord, je voudrais savoir si c'est possible en utilisant l'un de PHP des fonctions. Deuxièmement, je voudrais voir une alternative.
  • Regardez: notmysock.org/blog/php/schwartzian-transform.html il résout mon problème.

InformationsquelleAutor Alin Purcaru | 2010-12-04
  1. 28

    Depuis PHP ne supporte pas le tri stable après PHP 4.1.0, vous devez écrire votre propre fonction.

    Ce qui semble faire ce que vous demandez: http://www.php.net/manual/en/function.usort.php#38827

    Que le manuel dit: "Si deux membres sont considérées comme égales, leur ordre dans le tableau trié est pas défini." Cela signifie que le tri n'est pas "stable" et peut modifier l'ordre des éléments qui permettent de comparer l'égalité.

    Parfois vous avez besoin d'un tri stable. Par exemple, si vous triez la liste par un champ, puis de les trier à nouveau par un autre champ, mais ne voulez pas perdre la commande du champ précédent. Dans ce cas, il est préférable d'utiliser usort avec une fonction de comparaison qui prend à la fois les champs de compte, mais si vous ne pouvez pas faire cela, alors utiliser la fonction ci-dessous. C'est une sorte de fusion, qui est garanti O(n*log(n)) de la complexité, ce qui signifie qu'il reste assez rapide même lorsque vous utilisez de grosses listes (à la différence de bubblesort et le tri par insertion, qui sont en 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;
}
?>

    On peut également trouver des ce fil du forum intéressant.

    • Le fil de discussion du forum n'est pas intéressant. Les autres parties ou de votre réponse.
    • c'est pourquoi je l'ai écrit, "peut trouve intéressant..." 🙂
    • en fait il va à la conclusion que toutes les méthodes décrites dans qui NE fonctionnent PAS. Donc dans un sens, nous ne savons pas à essayer ces méthodes. Utile en ce sens.
    • Je pense que vous devriez vous attribuer votre source. J'ai trouvé cette méthode dupliqué ici.
    • Veuillez voir @Martijn réponse, qui utilise la décoration et de l' uasort avec un enveloppé fonction de comparaison, et prend 1/5ème du temps que cette réponse (qui est une excellente illustration, mais inneficient).
    • $tableau2[0] échoue si cette clé existe. Il semble que cette solution a une restriction qui doit être.

    InformationsquelleAutor shamittomar
  2. 11

    array_multisort est très pratique, il suffit d'utiliser un ensemble ordonné de gamme comme le deuxième tableau ($order est que temporaire, il sert à l'ordre de l'équivalent des éléments du premier tableau dans l'ordre d'origine):

    $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);

    Sortie

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

    J'ai utilisé des données de test avec pas-clés des commandes de démontrer qu'il fonctionne correctement. Néanmoins, ici, c'est la sortie de votre script de test:

    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
)

    Inconvénient

    Il ne fonctionne qu'avec des comparaisons, vous ne pouvez pas utiliser votre propre fonction de comparaison. Les valeurs possibles (deuxième paramètre de array_multisort()) sont:

    Type de classement des drapeaux:

    • SORT_ASC - trier les éléments ascendingly.
    • SORT_DESC - trier les éléments descendingly.
    • SORT_REGULAR - comparer les éléments normalement (ne pas modifier les types)
    • SORT_NUMERIC - comparer les objets numériquement
    • SORT_STRING - comparer les objets comme des chaînes
    • SORT_LOCALE_STRING - comparer les objets comme des chaînes de caractères, en fonction de la configuration locale. Il utilise les paramètres régionaux, qui peuvent être modifiés à l'aide de
      setlocale()
    • SORT_NATURAL - comparer les objets comme des chaînes de caractères à l'aide de "ordre naturel" comme natsort()
    • SORT_FLAG_CASE - peuvent être combinés (OU binaire) avec SORT_STRING ou SORT_NATURAL pour trier les chaînes de cas insensiblement
    • Vous pouvez également utiliser array_sort($a, SORT_ASC, array_keys($a), SORT_NATURAL) pour une forme similaire de la stabilité de tri. Qui change [ 'Sick' => 8, 'Vacation' => 12, 'Other' => -4, 'Holiday' => 0, 'Bereavement' => 0 ] à [ 'Other' => -4, 'Bereavement' => 0, 'Holiday' => 0, 'Sick' => 8, 'Vacation' => 12 ]
    InformationsquelleAutor Fabian Schmengler
  3. 7

    Référence pour l'avenir, j'ai mis un ensemble de tri stable variantes de builtin fonctions de PHP sur Github: https://github.com/vanderlee/PHP-stable-sort-functions, basé sur @Jack solution et quelques autres trucs.

    InformationsquelleAutor Martijn
  4. 5

    Par souci d'exhaustivité, vous devriez également vérifier la Schwartzian transformer:

    //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
}

    L'algorithme de tri par défaut de PHP fonctionne très bien avec les tableaux, à cause de cela:

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

    Si vous souhaitez utiliser vos propres critères de tri que vous pouvez utiliser uasort() ainsi:

    //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
    }
}
    • Veuillez noter que le Piège dans la question. Vous ne devez pas compter sur les touches pour être commandés dans le tableau d'origine.
    • Bon, assez juste. Édité 🙂
    InformationsquelleAutor Ja͢ck
  5. 1

    C'est une solution à l'aide de laquelle vous pouvez atteindre tri stable dans la fonction 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;
}
    InformationsquelleAutor Senchu Thomas
  6. 0

    Juste pour compléter les réponses, avec des cas très spécifiques. Si les clés du tableau de $array sont par défaut, alors qu'un simple array_values(asort($array)) est suffisante (ici, par exemple, dans l'ordre croissant)

    InformationsquelleAutor epsilones