Une fonction de tri stable

L’algorithme de la plupart des méthodes de tri du langage PHP n'est pas stable, c'est à dire qu'il ne préserve pas l'ordre relatif des éléments ayant les mêmes valeurs. Sans importance la plupart du temps, il est des cas où l'on a besoin d'ordonner des valeurs selon un poids et l'ordre dans lequel elles ont été définies. Je vous propose une fonction répondant à cette exigence.

Mise en évidence de l'instabilité

La plupart des fonctions de tri de PHP, comme la fonction asort(), utilisent l'algorithme quicksort, c'est un des plus rapides mais il a un inconvénient majeur. Parce qu'il utilise un pivot, les éléments qui ont la même valeur peuvent être mélangés.

Le code suivant démontre cet effet sur un tableau associatif dont toutes les valeurs sont égales :

<?php

$a = array(1,1,1);

var_dump($a);

asort($a);

var_dump($a);

En comparant l'affichage du tableau initial à celui du tableau trié on voit clairement l'effet du pivot, le tableau se retrouve à l'envers !

array
  0 => int 1
  1 => int 1
  2 => int 1

array
  2 => int 1
  1 => int 1
  0 => int 1

Puisqu'on ne va pas s'amuser à écrire un algorithme de tri en PHP, qui serait certes efficace mais couteux en temps machine, on va devoir trouver une solution avec ce que l'on a.

Des tableaux pour valeurs

Les fonctions de tri s'appliquent aussi aux tableaux associatifs dont les valeurs sont elles-mêmes des tableaux, dans ce cas la comparaison est récursive :

<?php

$a = array(array(32)array(33)array(31));

var_dump($a);
array
  3 => 
    array
      0 => int 3
      1 => int 1
  1 => 
    array
      0 => int 3
      1 => int 2
  2 => 
    array
      0 => int 3
      1 => int 3

Les éléments sont triés comme nous le souhaitions puisque nous avons [3, 1], [3, 2] et [3, 3].

En construisant des valeurs temporaires à partir des valeurs à comparer et de leur clé nous pourrions trier le tableau tout en conservant l'ordre relatif des éléments. Parce que les clés sont uniques, les comparaisons valeur + clé ne peuvent produire d'exéco.

Changer de valeur pour contourner le problème

La fonction array_walk() permet d'exécuter une fonction sur chacun des éléments d'un tableaux mais surtout, et c'est là le plus important, les valeurs lui sont passées par référence, c'est à dire qu'il nous est possible de modifier ces valeurs en place. Nous pourrions avoir deux fonctions : une qui transforme les valeurs en tableau [valeur, clé], et une qui restaure les valeurs une fois le tri terminé.

<?php

$transform = function(&$v$k)
{
    $v = array($v$k);
};

$restore = function(&$v$k)
{
    $v = $v[0];
};

Une fonction de tri stable avec un cadeau bonux

La fonction stable_sort() permet de trier les valeurs d'un tableau associatif tout en conservant l'ordre relatif des éléments ainsi que les clés du tableau. Elle permet par ailleurs de définir la fonction à utiliser pour extraire la valeur à comparer, parce que bien souvent lorsque les valeurs sont des tableaux, la valeur à comparer n'est pas forcément la première du tableau.

<?php

stable_sort(&$array$picker=null)
{
    static $transform$restore;

    if (!$transform)
    {
        $transform = function(&$v$k)
        {
            $v = array($v$k$v);
        };

        $restore = function(&$v$k)
        {
            $v = $v[2];
        };
    }

    if ($picker)
    {
        array_walk
        (
            $arrayfunction(&$v$k) use ($picker)
            {
                $v = array($picker($v)$k$v);
            }
        );
    }
    else
    {
        array_walk($array$transform);
    }

    asort($array);

    array_walk($array$restore);
}

Voyons ce que cela donne sur un groupe de chanteuses :

array
(
    array(1, 'madonna'),
    array(1, 'madonna'),
    array(1, 'britney'),
    array(0, 'gaga')
);

Résultat du tri avec la fonction asort() :

array
  3 => 
    array
      0 => int 0
      1 => string 'gaga' (length=4)
  2 => 
    array
      0 => int 1
      1 => string 'britney' (length=7)
  1 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)
  0 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)

Le premier « madonna » (index 0) se trouve en fin de tableau alors qu'il était placé avant le second « madonna » (index 1).

Résultat du tri avec la fonction stable_sort():

array
  3 => 
    array
      0 => int 0
      1 => string 'gaga' (length=4)
  2 => 
    array
      0 => int 1
      1 => string 'britney' (length=7)
  0 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)
  1 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)

Avec la fonction stable_sort() les valeurs sont triées correctement et l'ordre relatif est respecté.

Utiliser une fonction de rappel pour choisir la valeur à comparer

Comme nous l'avions évoqué, la fonction stable_sort() donne la possibilité de définir la fonction à utiliser pour choisir la valeur à comparer.

Reprenons notre tableau précédent mais cette fois-ci comparons uniquement les noms de ses chanteuses sinon fameuses du moins célèbres :

<?php

$a = array
(
    array(1'madonna'),
    array(1'madonna'),
    array(1'britney'),
    array(0'gaga')
);

stable_sort($afunction($v) { return $v[1]});
array
  2 => 
    array
      0 => int 1
      1 => string 'britney' (length=7)
  3 => 
    array
      0 => int 0
      1 => string 'gaga' (length=4)
  0 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)
  1 => 
    array
      0 => int 1
      1 => string 'madonna' (length=7)

Comme la comparaison est faite uniquement sur le nom, « britney » est en première position suivi de « gaga » puis deux « madonna ». On notera que l'ordre relatif des « madonna » est respecté puisque l'index 0 arrive avant l'index 1.

Le code de la fonction stable_sort() est également disponible sur GitHub : stable_sort.php.

Laisser un commentaire

Pas de commentaire