Aux chapitres 6 et 7 nous avons étudié plusieurs algorithmes de tri, dont l’analyse se concluait souvent par le même refrain :
Cette constance à de quoi interroger : y a-t-il quelque chose dans le problème même du tri qui ferait que des algorithmes si différents que le tri fusion, le tri rapide et le tri par tas s’accordent sur cette complexité ?
Concentrons-nous sur une opération centrale, commune à tous ces algorithmes : la comparaison de deux éléments du tableau à trier. Cette opération apparaît avec diverses finalités selon l’algorithme :
◆ pour choisir le prochain élément d’un tableau fusionné dans le tri fusion,
◆ pour choisir le paquet où placer un élément dans le tri rapide,
◆ pour choisir la manière de réarranger les éléments du tas dans le tri par tas,
◆ etc.
Dans tous les cas, cependant, ce test est incorporé à une instruction de branchement générant, selon le résultat du test, deux comportements possibles. La succession des tests réalisés par un algorithme permet alors de choisir entre toutes les issues possibles de l’exécution de l’algorithme.
Pour une entrée d’une taille N fixée, on peut finalement résumer chacun de ces algorithmes de tri par un arbre binaire, appelé questionnaire, où :
◆ chaque nœud interne correspond à une comparaison,
◆ les deux sous-arbres gauche et droit d’un nœud correspondent aux deux comportements suivant l’issue positive ou négative de la comparaison,
◆ chaque feuille, ou de manière équivalente chaque chemin de la racine à une feuille, correspond à une exécution complète et à son résultat…