Page d'accueil	encyclopedie-enligne.com en page d'accueil
Liste Articles: [0-A] [A-C] [C-F] [F-J] [J-M] [M-P] [P-S] [S-Z] | Liste Catégories | Une page au hasard | Pages liées

Tri arborescent

Soit à classer par ordre alphabétique ou numérique une série d'éléments (nombres ou mots), par exemple lundi, mardi, mercredi, jeudi, vendredi, samedi, dimanche.

Une façon très inefficace de les classer serait de comparer chaque élément à tous les autres, ce qui se nomme un tri en N².

Une façon plus rationnelle est de faire usage du fait que lorsqu'une clé est supérieure à une autre, elle est forcément aussi supérieure à toutes celles qui lui étaient inférieures sans qu'il soit besoin de les comparer. C'est le principe même de l'arborescence. Sur des grands ensembles, on peut éviter ainsi quelques dizaines de millions d'opértaions qui auraient été inutiles, et ramener un tri de quelques heures à quelques minutes, de quelques minutes à quelques secondes, ou de quelques secondes à un temps qui devient inobservable pour l'utilisateur.

Convenons donc de mettre à gauche d'une clé toutes celles qui lui sont inférieures, et à droite toutes celles qui lui sont supérieures, et ainsi de suite récursivement. Notre arbre des jours ouvrés va avoir l'allure suivante :

 lundi
 jeudi mardi 
 dimanche mercredi
 vendredi
 samedi

Comment afficher maintenant la liste triée que nous cherchions ? En spécifiant l'ordre d'affichage ainsi :

 sub Lister-les-clés (racine)
 si existe sous-arbre-à-gauche alors Lister-les-clés sous-arbre-à-gauche;
 imprimer la clé associée à la racine
 si existe sous-arbre-à-droite alors Lister-les-clés sous-arbre-à-droite;
 fin-sub

On obtient bien :

dimanche
jeudi
lundi
mardi
mercredi
samedi
vendredi

L'intérêt de cet exemple est bien entendu purement pédagogique : personne ne programme jamais de tri dans un programme applicatif, la fonction de tri faisant partie des primitives de base de tout langage vraiment évolué (Perl, APL, etc.).

• On démontre que dans le cas d'une entrée en ordre vraiment aléatoire (en particulier autre chose que celui où toutes les clés sont déjà triées à l'exception de quelques-unes!), ce tri est en N log N.
• On démontre aussi qu'on ne peut pas effectuer de tri plus vite qu'en N log N, puisque trier N valeurs correspond à en choisir une permutation parmi N! (factorielle N) possibles, et que log₂ N! croît en N log N. On ne peut espérer déterminer ces N log N bits sans effectuer N log N tests qui précisément apportent chacun 1 bit.
• Des algorithmes de rotation existent pour faire face le moins mal possible aux cas mal conditionnés. Voir Knuth, The Art of Computer Programming' vol. 1 « Fundamental Algorithms ».