Comment trier les tableaux et les données en PHP ?

Question

Cette question est destinée à servir de référence pour les questions relatives au tri des tableaux en PHP. Il est facile de penser que votre cas particulier est unique et mérite une nouvelle question, mais la plupart sont en fait des variations mineures de l'une des solutions de cette page.

Si votre question est fermée parce qu'elle fait double emploi avec celle-ci, demandez à ce qu'elle soit rouverte uniquement si vous pouvez expliquer pourquoi elle diffère sensiblement de toutes les questions ci-dessous.

Comment trier un tableau en PHP ?
Comment trier un complexe tableau en PHP ?
Comment trier un tableau d'objets en PHP ?

---

1. Tableaux unidimensionnels de base ; y compris les tableaux multidimensionnels, y compris les tableaux d'objets ; y compris le tri d'un tableau en fonction d'un autre.

2. Triage avec SPL

3. Tri stable

Pour la réponse pratique utilisant les fonctions existantes de PHP, voir 1., pour la réponse académique détaillée sur les algorithmes de tri (que les fonctions de PHP implémentent et que vous ), voir 2. mai nécessaire pour les cas vraiment, vraiment complexes), voir 2.

Answer 1

Tableaux unidimensionnels de base

$array = array(3, 5, 2, 8);

Fonctions de tri applicables :

• sort
• rsort
• asort
• arsort
• natsort
• natcasesort
• ksort
• krsort

La différence entre les deux consiste simplement à savoir si les associations clé-valeur sont conservées (le " a "), qu'il trie de bas en haut ou inversement (fonctions " r "), qu'il trie les valeurs ou les clés (" k ") et comment il compare les valeurs (" nat " vs. normal). Voir http://php.net/manual/en/array.sorting.php pour une vue d'ensemble et des liens vers des informations plus détaillées.

Tableaux multidimensionnels, y compris les tableaux d'objets

$array = array(
    array('foo' => 'bar', 'baz' => 42),
    array('foo' => ...,   'baz' => ...),
    ...
);

Si vous voulez trier $array par la clé 'foo' de chaque entrée, vous avez besoin d'une fonction de comparaison personnalisée . Ce qui précède sort et les fonctions connexes travaillent sur des valeurs simples qu'ils savent comparer et trier. PHP ne sait pas simplement "savoir" quoi faire avec un fichier valeur complexe como array('foo' => 'bar', 'baz' => 42) pourtant ; il faut donc le dire.

Pour ce faire, vous devez créer un fonction de comparaison . Cette fonction prend deux éléments et doit retourner 0 si ces éléments sont considérés comme égaux, une valeur inférieure à 0 si la première valeur est inférieure et une valeur supérieure à 0 si la première valeur est supérieure. C'est tout ce qui est nécessaire :

function cmp(array $a, array $b) {
    if ($a['foo'] < $b['foo']) {
        return -1;
    } else if ($a['foo'] > $b['foo']) {
        return 1;
    } else {
        return 0;
    }
}

Souvent, vous voudrez utiliser un fonction anonyme en tant que rappel. Si vous souhaitez utiliser une méthode ou une méthode statique, reportez-vous à l'onglet autres façons de spécifier un callback en PHP .

Vous utilisez ensuite l'une de ces fonctions :

• usort
• uasort
• uksort

Là encore, ils ne diffèrent que par le fait qu'ils conservent les associations clé-valeur et qu'ils trient par valeurs ou par clés. Lisez leur documentation pour plus de détails.

Exemple d'utilisation :

usort($array, 'cmp');

usort va prendre deux éléments du tableau et appeler votre cmp avec eux. Donc cmp() sera appelé avec $a como array('foo' => 'bar', 'baz' => 42) y $b comme un autre array('foo' => ..., 'baz' => ...) . La fonction retourne ensuite à usort laquelle des valeurs était la plus grande ou si elles étaient égales. usort répète ce processus en passant différentes valeurs pour $a y $b jusqu'à ce que le tableau soit trié. Le site cmp sera appelée plusieurs fois, au moins autant de fois qu'il y a de valeurs dans $array avec différentes combinaisons de valeurs pour $a y $b à chaque fois.

Pour vous habituer à cette idée, essayez ceci :

function cmp($a, $b) {
    echo 'cmp called with $a:', PHP_EOL;
    var_dump($a);
    echo 'and $b:', PHP_EOL;
    var_dump($b);
}

Tout ce que vous avez fait est de définir un moyen personnalisé de comparer deux éléments, c'est tout ce dont vous avez besoin. Cela fonctionne avec toutes sortes de valeurs.

Au fait, cela fonctionne avec n'importe quelle valeur, les valeurs ne doivent pas nécessairement être des tableaux complexes. Si vous souhaitez effectuer une comparaison personnalisée, vous pouvez également le faire sur un simple tableau de chiffres.

sort trie par référence et ne retourne rien d'utile !

Notez que le tableau trie en place vous n'avez pas besoin d'affecter la valeur de retour à quoi que ce soit. $array = sort($array) remplacera le tableau par true mais pas avec un tableau trié. Juste sort($array); travaux.

Comparaisons numériques personnalisées

Si vous voulez trier par le baz qui est numérique, tout ce que vous avez à faire est de :

function cmp(array $a, array $b) {
    return $a['baz'] - $b['baz'];
}

Merci à Le PoWEr des MATHs ceci renvoie une valeur < 0, 0 ou > 0 selon que $a est inférieur, égal ou supérieur à $b .

Notez que cela ne fonctionnera pas bien pour float puisqu'elles seront réduites à une valeur de int et perdre la précision. Utilisez un langage explicite -1 , 0 y 1 à la place des valeurs de retour.

Objets

Si vous avez un tableau d'objets, cela fonctionne de la même manière :

function cmp($a, $b) {
    return $a->baz - $b->baz;
}

Fonctions

Vous pouvez faire tout ce dont vous avez besoin à l'intérieur d'une fonction de comparaison, y compris appeler des fonctions :

function cmp(array $a, array $b) {
    return someFunction($a['baz']) - someFunction($b['baz']);
}

Cordes

Un raccourci pour la première version de comparaison de chaînes de caractères :

function cmp(array $a, array $b) {
    return strcmp($a['foo'], $b['foo']);
}

strcmp fait exactement ce que l'on attend d'elle cmp ici, il renvoie -1 , 0 ou 1 .

Opérateur de vaisseau spatial

PHP 7 a introduit l'option opérateur de vaisseau spatial qui unifie et simplifie les comparaisons de type égal/plus petit/plus grand :

function cmp(array $a, array $b) {
    return $a['foo'] <=> $b['foo'];
}

Tri par champs multiples

Si vous voulez trier principalement par foo mais si foo est égale pour deux éléments triés par baz :

function cmp(array $a, array $b) {
    if (($cmp = strcmp($a['foo'], $b['foo'])) !== 0) {
        return $cmp;
    } else {
        return $a['baz'] - $b['baz'];
    }
}

Pour ceux qui sont familiers, ceci est équivalent à une requête SQL avec ORDER BY foo, baz .
Voir aussi cette version abrégée très soignée y Comment créer dynamiquement une telle fonction de comparaison pour un nombre arbitraire de clés ? .

Triage dans un ordre manuel et statique

Si vous voulez trier les éléments dans un "ordre manuel" comme "foo", "bar", "baz" :

function cmp(array $a, array $b) {
    static $order = array('foo', 'bar', 'baz');
    return array_search($a['foo'], $order) - array_search($b['foo'], $order);
}

---

Pour tout ce qui précède, si vous utilisez PHP 5.3 ou plus (et vous devriez vraiment le faire), utilisez les fonctions anonymes pour un code plus court et pour éviter d'avoir une autre fonction globale flottant autour :

usort($array, function (array $a, array $b) { return $a['baz'] - $b['baz']; });

Voilà à quel point le tri d'un tableau multidimensionnel complexe peut être simple. Encore une fois, il suffit de penser en termes de apprendre à PHP comment dire lequel de deux éléments est le plus grand. ; laissez PHP faire le tri réel.

De même, pour tout ce qui précède, pour passer de l'ordre ascendant à l'ordre descendant, il suffit d'intervertir les paramètres suivants $a y $b des arguments autour. Par exemple :

return $a['baz'] - $b['baz']; // ascending
return $b['baz'] - $a['baz']; // descending

Trier un tableau en fonction d'un autre

Et puis il y a l'étrange array_multisort qui vous permet de trier un tableau en fonction d'un autre :

$array1 = array( 4,   6,   1);
$array2 = array('a', 'b', 'c');

Le résultat attendu ici serait :

$array2 = array('c', 'a', 'b');  // the sorted order of $array1

Utilice array_multisort pour y arriver :

array_multisort($array1, $array2);

A partir de PHP 5.5.0, vous pouvez utiliser array_column pour extraire une colonne d'un tableau multidimensionnel et trier le tableau sur cette colonne :

array_multisort(array_column($array, 'foo'), SORT_DESC, $array);

Vous pouvez également trier sur plus d'une colonne, chacune dans un sens ou dans l'autre :

array_multisort(array_column($array, 'foo'), SORT_DESC,
                array_column($array, 'bar'), SORT_ASC,
                $array);

Depuis PHP 7.0.0, vous pouvez également extraire les propriétés d'un tableau d'objets.

---

_{Si vous avez des cas plus courants, n'hésitez pas à modifier cette réponse.}

Answer 2

Les méthodes les plus élémentaires sont déjà couvertes par deceze J'essaierais de regarder d'autres types de tri.

Triage avec SPL

SplHeap

class SimpleHeapSort extends SplHeap {
    public function compare($a, $b) {
        return strcmp($a, $b);
    }
}

// Let's populate our heap here (data of 2009)
$heap = new SimpleHeapSort();
$heap->insert("a");
$heap->insert("b");
$heap->insert("c");

echo implode(PHP_EOL, iterator_to_array($heap));

Sortie

c
b
a

SplMaxHeap

La classe SplMaxHeap fournit les principales fonctionnalités d'un tas, en gardant le maximum au sommet.

$heap = new SplMaxHeap();
$heap->insert(1);
$heap->insert(2);
$heap->insert(3);

SplMinHeap

La classe SplMinHeap fournit les principales fonctionnalités d'un tas, en gardant le minimum au sommet.

$heap = new SplMinHeap ();
$heap->insert(3);
$heap->insert(1);
$heap->insert(2);

Autres types de tri

Tri à bulles

De la Article de Wikipédia sur le tri à bulles :

Le tri à bulles, parfois appelé à tort tri par coulée, est un algorithme de tri simple qui fonctionne en parcourant de manière répétée la liste à trier, en comparant chaque paire d'éléments adjacents et en les échangeant s'ils sont dans le mauvais ordre. Le passage dans la liste est répété jusqu'à ce qu'aucun échange ne soit nécessaire, ce qui indique que la liste est triée. L'algorithme tire son nom de la façon dont les éléments les plus petits "remontent" en haut de la liste. Comme il n'utilise que des comparaisons pour opérer sur les éléments, il s'agit d'un tri par comparaison. Bien que cet algorithme soit simple, la plupart des autres algorithmes de tri sont plus efficaces pour les grandes listes.

function bubbleSort(array $array) {
    $array_size = count($array);
    for($i = 0; $i < $array_size; $i ++) {
        for($j = 0; $j < $array_size; $j ++) {
            if ($array[$i] < $array[$j]) {
                $tem = $array[$i];
                $array[$i] = $array[$j];
                $array[$j] = $tem;
            }
        }
    }
    return $array;
}

Tri de sélection

Desde l'article de Wikipédia sur le tri sélectif :

En informatique, le tri sélectif est un algorithme de tri, plus précisément un tri par comparaison in situ. Sa complexité temporelle est de O(n2), ce qui le rend inefficace sur les grandes listes, et ses performances sont généralement inférieures à celles du tri par insertion. Le tri par sélection est réputé pour sa simplicité, et il présente des avantages en termes de performances par rapport à des algorithmes plus complexes dans certaines situations, notamment lorsque la mémoire auxiliaire est limitée.

function selectionSort(array $array) {
    $length = count($array);
    for($i = 0; $i < $length; $i ++) {
        $min = $i;
        for($j = $i + 1; $j < $length; $j ++) {
            if ($array[$j] < $array[$min]) {
                $min = $j;
            }
        }
        $tmp = $array[$min];
        $array[$min] = $array[$i];
        $array[$i] = $tmp;
    }
    return $array;
}

Tri par insertion

De la Article de Wikipédia sur le tri d'insertion :

Le tri par insertion est un algorithme de tri simple qui construit le tableau (ou la liste) trié final un élément à la fois. Il est beaucoup moins efficace sur les grandes listes que les algorithmes plus avancés tels que quicksort, heapsort ou merge sort. Cependant, le tri par insertion présente plusieurs avantages :

function insertionSort(array $array) {
    $count = count($array);
    for($i = 1; $i < $count; $i ++) {

        $j = $i - 1;
        // second element of the array
        $element = $array[$i];
        while ( $j >= 0 && $array[$j] > $element ) {
            $array[$j + 1] = $array[$j];
            $array[$j] = $element;
            $j = $j - 1;
        }
    }
    return $array;
}

Shellsort

De la Article de Wikipedia sur Shellsort :

Shellsort, également connu sous le nom de Shell sort ou de la méthode Shell, est un tri par comparaison en place. Il généralise un tri par échange, comme le tri par insertion ou le tri à bulles, en commençant la comparaison et l'échange d'éléments par des éléments éloignés les uns des autres avant de terminer par des éléments voisins.

function shellSort(array $array) {
    $gaps = array(
            1,
            2,
            3,
            4,
            6
    );
    $gap = array_pop($gaps);
    $length = count($array);
    while ( $gap > 0 ) {
        for($i = $gap; $i < $length; $i ++) {
            $tmp = $array[$i];
            $j = $i;
            while ( $j >= $gap && $array[$j - $gap] > $tmp ) {
                $array[$j] = $array[$j - $gap];
                $j -= $gap;
            }
            $array[$j] = $tmp;
        }
        $gap = array_pop($gaps);
    }
    return $array;
}

Triage par peigne

Desde l'article de Wikipédia sur le peigne :

Comb sort est un algorithme de tri relativement simple conçu à l'origine par Wlodzimierz Dobosiewicz en 1980. Il a ensuite été redécouvert par Stephen Lacey et Richard Box en 1991. Le tri en peigne améliore le tri à bulles.

function combSort(array $array) {
    $gap = count($array);
    $swap = true;
    while ( $gap > 1 || $swap ) {
        if ($gap > 1)
            $gap /= 1.25;
        $swap = false;
        $i = 0;
        while ( $i + $gap < count($array) ) {
            if ($array[$i] > $array[$i + $gap]) {
                // swapping the elements.
                list($array[$i], $array[$i + $gap]) = array(
                        $array[$i + $gap],
                        $array[$i]
                );
                $swap = true;
            }
            $i ++;
        }
    }
    return $array;
}

Triage par fusion

Desde l'article de Wikipédia sur le tri par fusion :

En informatique, un tri par fusion (aussi communément appelé mergesort) est un algorithme de tri par comparaison en O(n log n). La plupart des implémentations produisent un tri stable, ce qui signifie que l'implémentation préserve l'ordre d'entrée des éléments égaux dans le résultat trié.

function mergeSort(array $array) {
    if (count($array) <= 1)
        return $array;

    $left = mergeSort(array_splice($array, floor(count($array) / 2)));
    $right = mergeSort($array);

    $result = array();

    while ( count($left) > 0 && count($right) > 0 ) {
        if ($left[0] <= $right[0]) {
            array_push($result, array_shift($left));
        } else {
            array_push($result, array_shift($right));
        }
    }
    while ( count($left) > 0 )
        array_push($result, array_shift($left));

    while ( count($right) > 0 )
        array_push($result, array_shift($right));

    return $result;
}

Quicksort

Desde l'article de Wikipédia sur le Quicksort :

Quicksort, ou partition-exchange sort, est un algorithme de tri développé par Tony Hoare qui, en moyenne, effectue O(n log n) comparaisons pour trier n éléments. Dans le pire des cas, il effectue O(n2) comparaisons, bien que ce comportement soit rare.

function quickSort(array $array) {
    if (count($array) == 0) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = array();
    for($i = 1; $i < count($array); $i ++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    return array_merge(quickSort($left), array(
            $pivot
    ), quickSort($right));
}

Tri par permutation

Desde l'article de Wikipédia sur le tri par permutation :

Le tri par permutation, qui procède en générant les permutations possibles du tableau/de la liste d'entrée jusqu'à ce qu'il trouve la permutation triée.

function permutationSort($items, $perms = array()) {
    if (empty($items)) {
        if (inOrder($perms)) {
            return $perms;
        }
    } else {
        for($i = count($items) - 1; $i >= 0; -- $i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $res = permutationSort($newitems, $newperms);
            if ($res) {
                return $res;
            }
        }
    }
}

function inOrder($array) {
    for($i = 0; $i < count($array); $i ++) {
        if (isset($array[$i + 1])) {
            if ($array[$i] > $array[$i + 1]) {
                return False;
            }
        }
    }
    return True;
}

Triage par radix

Desde l'article de Wikipedia sur Radix sort :

En informatique, le tri radix est un algorithme de tri non comparatif des nombres entiers qui trie les données avec des clés entières en regroupant les clés par les chiffres individuels qui partagent la même position significative et la même valeur.

// Radix Sort for 0 to 256
function radixSort($array) {
    $n = count($array);
    $partition = array();

    for($slot = 0; $slot < 256; ++ $slot) {
        $partition[] = array();
    }

    for($i = 0; $i < $n; ++ $i) {
        $partition[$array[$i]->age & 0xFF][] = &$array[$i];
    }

    $i = 0;

    for($slot = 0; $slot < 256; ++ $slot) {
        for($j = 0, $n = count($partition[$slot]); $j < $n; ++ $j) {
            $array[$i ++] = &$partition[$slot][$j];
        }
    }
    return $array;
}

Answer 3

Tri stable

Disons que vous avez un tableau comme celui-ci :

['Kale', 'Kaleidoscope', 'Aardvark', 'Apple', 'Leicester', 'Lovely']

Et maintenant vous voulez trier sur la première lettre seulement :

usort($array, function($a, $b) {
    return strcmp($a[0], $b[0]);
});

Le résultat est le suivant :

['Apple', 'Aardvark', 'Kale', 'Kaleidoscope', 'Lovely', 'Leicester']

Le tri n'était pas stable !

L'observateur attentif aura peut-être remarqué que l'algorithme de tri des tableaux (QuickSort) ne produit pas un résultat stable et que l'ordre original entre les mots de même première lettre n'est pas préservé. Ce cas est trivial et nous aurions dû comparer la chaîne entière, mais supposons que votre cas d'utilisation est plus compliqué, comme deux tris consécutifs sur des champs différents qui ne devraient pas annuler le travail de l'autre.

La transformation schwartzienne

La transformation schwartzienne Le principe du tri stable, également connu sous le nom d'idiome de la décoration, du tri et de la sous-décoration, a pour effet de rendre un tri stable avec un algorithme de tri intrinsèquement instable.

Tout d'abord, vous décorez chaque élément du tableau avec un autre tableau comprenant une clé primaire (la valeur) et une clé secondaire (son index ou sa position) :

array_walk($array, function(&$element, $index) {
    $element = array($element, $index); // decorate
});

Cela transforme le tableau en ceci :

[
    ['Kale', 0], ['Kaleidoscope', 1], 
    ['Aardvark', 2], ['Apple', 3], 
    ['Leicester', 4], ['Lovely', 5]
]

Maintenant, nous ajustons l'étape de comparaison ; nous comparons à nouveau la première lettre, mais si elles sont identiques, la clé secondaire est utilisée pour conserver l'ordre original :

usort($array, function($a, $b) {
    // $a[0] and $b[0] contain the primary sort key
    // $a[1] and $b[1] contain the secondary sort key
    $tmp = strcmp($a[0][0], $b[0][0]);

    if ($tmp != 0) {
        return $tmp; // use primary key comparison results
    }

    return $a[1] - $b[1]; // use secondary key
});

Ensuite, on défait la décoration :

array_walk($array, function(&$element) {
    $element = $element[0];
});

Le résultat final :

['Aardvark', 'Apple', 'Kale', 'Kaleidoscope', 'Leicester', 'Lovely']

Qu'en est-il de la réutilisation ?

Vous avez dû réécrire votre fonction de comparaison pour qu'elle fonctionne avec les éléments transformés du tableau ; vous ne voulez peut-être pas modifier vos fonctions de comparaison délicates, alors voici un emballage pour la fonction de comparaison :

function stablecmp($fn)
{
    return function($a, $b) use ($fn) {
        if (($tmp = call_user_func($fn, $a[0], $b[0])) != 0) {
            return $tmp;
        } else {
            return $a[1] - $b[1];
        }
    };
}

Écrivons l'étape de tri en utilisant cette fonction :

usort($array, stablecmp(function($a, $b) {
    return strcmp($a[0], $b[0]);
}));

Voilà ! Votre code de comparaison immaculé est de retour.

Answer 4

Depuis PHP 5.3, avec les fermetures, il est également possible d'utiliser une fermeture pour déterminer l'ordre de votre tri.

Par exemple, supposons que $array est un tableau d'objets contenant une propriété de mois.

 $orderArray = array("Jan","Feb","Mar","Apr","May","June","July","Aug","Sept","Oct","Nov","Dec");

 usort($array, function($a, $b) use ($orderArray){
       return array_search($a->month, $orderArray) - array_search($b->month, $orderArray);
 });

Answer 5

LINQ

Dans .NET, LINQ est fréquemment utilisé pour le tri, qui fournit une syntaxe beaucoup plus agréable que les fonctions de comparaison, en particulier lorsque les objets doivent être triés par plusieurs champs. Il existe plusieurs portages de LINQ en PHP, notamment YaLinqo bibliothèque*. Avec elle, les tableaux peuvent être triés en une seule ligne sans avoir à écrire des fonctions de comparaison complexes.

$sortedByName         = from($objects)->orderBy('$v->name');
$sortedByCount        = from($objects)->orderBy('$v->count');
$sortedByCountAndName = from($objects)->orderBy('$v->count')->thenBy('$v->name');

Les comparaisons peuvent être personnalisées davantage en passant un callback comme deuxième argument, par exemple :

$sortedByFilenameNat  = from($objects)->orderBy('$v->filename', 'strnatcmp');

Ici, '$v->count' est un raccourci pour function ($v) { return $v->count; } (l'un ou l'autre peut être utilisé). Ces chaînes de méthodes renvoient des itérateurs, les itérateurs peuvent être transformés en tableaux en ajoutant ->toArray() à la fin si nécessaire.

En interne, orderBy et les méthodes connexes font appel à des fonctions de tri de tableau appropriées ( uasort , krsort , multisort , usort etc.).

LINQ contient de nombreuses autres méthodes inspirées de SQL : filtrage, regroupement, jonction, agrégation, etc. Il est le mieux adapté aux cas où des transformations complexes sur des tableaux et des objets doivent être effectuées sans s'appuyer sur des bases de données.

_{* développé par moi, voir le fichier readme pour plus de détails et la comparaison avec d'autres ports LINQ}