Électronique Digérateur Science 2000+
Le oueblogue de #devroom@ulminfo.fr

Tri économe

C’est un fait bien connu : un tri par comparaisons doit effectuer au moins comparaisons.

Dans un cours d’algo, tout le monde regarde ses notes et constate que le dernier cours sur le tri fusion se termine ainsi : « (…)  ». Le problème du tri est résolu, on passe au TD.

Au-delà des grandes lettres rondes

Concrètement, que sont ces et lorsque prend la valeur choisie au hasard de par exemple? Y a-t-il quelque chose entre les deux? Le tri est une opération tellement commune, ça vaut le coup de l’optimiser autant que possible!

Parmi les algorithmes de tri par comparaisons, dans leurs pires cas respectifs, lesquels en font absolument le moins? Appelons éco-tri (pour un tri économe™) un tel tri, et notons donc le nombre maximum de comparaisons nécessaires pour éco-trier éléments.

Minorant, rappel

Si on fixe le nombre d’éléments à trier, tout algorithme de tri peut-être vu comme une descente dans un arbre de décision. On commence à la racine, qui indique deux éléments et à comparer, et on descend à gauche si , à droite sinon1; on recommence dans le sous-arbre suivant jusqu’à atteindre une feuille qui détient l’unique permutation des éléments qui soit compatible avec les résultats des comparaisons faites sur le chemin.

si a < b alors si b < c alors a, b, c sinon si a < c alors a, c, b sinon c, a, b
                   sinon si a < c alors b, a, c sinon si b < c alors b, c, a sinon c, b, a
Arbre de décision pour un tri de trois éléments.

Pour qu’un tel arbre donne un tri correct, toutes les permutations des entrées doivent figurer dans les feuilles, qui sont donc au nombre de .

Finalement, l’arbre étant binaire, on a une inégalité liant la profondeur au nombre de feuilles. Or, la profondeur d’un arbre de décision correspond exactement au nombre de comparaisons à effectuer dans le pire cas. On en déduit le minorant :

Majorant simple

Déjà est majoré par les complexités des tris que l’on connaît déjà, comme le tri fusion :

Voilà un premier encadrement. Bien évidemment, quand les encadrants sont égaux on en déduit l’encadré. Mais ça ne va pas loin.

1 2 3 4 5 6 7 8 9 10
0 1 3 5 8 11 14 17 21 25
0 1 3 5 ? ? ? ? ? ?
0 1 3 5 7 10 13 16 19 22

En fait, le tri fusion est le plus proche du minorant parmi les algorithmes de tri les plus connus2, à égalité avec le tri par insertion! L’arnaque : comme on compte seulement les comparaisons, décaler des éléments dans un tableau est une opération de bureaucratie, qui ne coûte rien. Évidemment, il faut alors effectuer l’insertion par dichotomie.

À l’étape , un nouvel élément est inséré parmi les précédents. On a donc

et on peut effectivement montrer que3


Tri de Ford-Johnson (1959)

Ford comme dans Ford-Fulkerson (flot maximum) et Bellman-Ford (plus courts chemins); Johnson comme dans Steinhaus-Johnson-Trotter (énumération de permutations).

Aussi appelé « tri fusion par insertion »; on espère du progrès en empruntant à ce qui se fait de mieux dans le domaine.

Première étape : partition

On partitionne les éléments en paires ordonnées disjointes (au coût d’autant de comparaisons), et éventuellement un élément à part que l’on notera .

Deuxième étape : tri récursif

On trie récursivement les paires selon leurs plus grands éléments. On peut alors les numéroter , tel que pour tout , on a .

Visualisation

Un ordre total peut être vu comme un graphe, et un tri par comparaisons cherche à le reconstituer en choisissant des arêtes à révéler, et en déduisant les autres par transitivité. Une objectif équivalent est de découvrir un chemin orienté entre chaque paire d’éléments.

Sous-ordre dévoilé après la deuxième étape.

Dernière étape : fusion par insertion

On insère les dans la chaîne des par recherche binaire, dans un ordre minimisant le nombre de comparaisons nécessaires.

s’insère gratuitement avant , on a :

Ensuite, et peuvent tous les deux s’insérer en deux comparaisons. Avant se trouvent en effet quatre interstices : avant , entre et , entre et , et entre et (voir la figure ci-dessus). Cependant, insérer puis nécessiterait en fait cinq insertions, contrairement à l’ordre inverse, puis , qui est le bon.

De la même manière, on insère pour trois comparaisons chacun; pour quatre; pour cinq; etc.

La suite des indices séparant ces groupes, dite de Jacobsthal, suit une simple relation de récurrence linéaire du second ordre :

Encadrement, bis

Il y a une formule donnant le nombre maximum de comparaisons du tri de Ford-Johnson :

Et il colle assez bien à notre minorant.

1 2 3 4 5 6 7 8 9 10 11
0 1 3 5 7 10 13 16 19 22 26
0 1 3 5 7 10 13 16 19 22 26
0 1 3 5 7 10 13 16 19 22 26

Trop beau

12 13 14 15 16 17 18 19 20 21 22 23
30 34 38 42 46 50 54 58 62 66 71 76
30 34 38 42 ? ? ? ? 62 66 71 ?
29 33 37 41 45 49 53 57 62 66 70 75

On a pour . Étonamment, il y a à nouveau égalité pour , mais elle disparaît pour de bon4 après .

Malgré les apparences de ces tableaux, l’algorithme de Ford-Johnson n’est pas un éco-tri en général.

Dans l’ordre chronologique, à coups de force brute électronique, on a trouvé :

  • 1965, ;
  • 1994, ;
  • 2004, , 5;
  • 2007, .

Donc l’algorithme de Ford-Johnson est un éco-tri pour ces valeurs, et que le minorant n’est pas optimal.


Références

  • The Art of Computer Programming, Vol. 3., Sorting and Searching, Knuth, 1998. Forcément. Contient un chapitre sur les tris optimaux.

  • Towards Optimal Sorting of 16 Elements, Peczarski, 2011. Un des rares papiers apparement libres sur le sujet.

  • A Tournament Problem, Ford, Johnson, 1959. L’origine de l’algorithme.

  • The Ford-Johnson algorithm is not optimal, Manacher, 1979. Le seul résumé trouvable mentionne la construction de contre-exemples pour .

  • http://www.xomnom.com/fja.html La page d’où je tire la description de l’algorithme, puisque je n’ai pas TACP sous la main.


Appendice

Que valent et lorsque ?

Réponse : Respectivement 2789479726208438316697774981126 et 280565481222168823727989709973. Tout ceci était un chipotage sur cet écart relatif inférieur à 0.6%.
Ford-Johnson prend 279112619665353928462337967605 comparaisons, avec un écart relatif au minorant de 0.06%. Le commerçant préférera donc parler du facteur 10.


  1. Les fanatiques de symétrie pourront supposer que tous les éléments sont distincts, ce qui n’apporte rien, ou considérer une comparaison trivaluée, (LT | EQ | GT), ce qui ne fait que compliquer les choses sans rien changer au résultat non plus.

  2. Tris par sélection, à bulles, au revoir. Le tri rapide est lent; lui rajouter un bon choix de pivot coûte trop cher. Le tri par tas a mangé un facteur 2, puisqu’il faut faire deux comparaisons pour déterminer l’enfant avec lequel on échange son parent.

  3. Y aurait-il une bijection naturelle entre les comparaisons des deux algorithmes?

  4. Je ne suis pas 100% sûr de ça en fait. Citation nécessaire. Je nJe ne trouve pas de contre-exemple pour .

  5. (Cet exposant n’est pas une puissance.) J’aimerais aussi savoir pourquoi 22. L’article convoité se trouve derrière un mur de péage.

  6. (Lui non plus.) Admirez aussi sa factorisation en nombres premiers : !