Les algorithmes de tri

Il est intéressant de constater qu'intuitivement, s'il lui est donné un ensemble à trier, tout un chacun met en place des stratégies de tri différentes selon le nombre d'éléments de l'ensemble, par exemple un jeu de 52 cartes ou 200 élèves à classer dans l'ordre alphabétique. Tri par sélection, tri par propagation, tri par insertion, tri rapide, tri par fusion... ces différentes méthodes ont chacune leurs particularités... et leur niveau de performance, qui correspond à la complexité de l'algorithme. La méthode la plus utilisée actuellement est sans doute la méthode de tri rapide ou Quicksort, qui a été inventée par Sir Charles Antony Richard Hoare en 1960 - d'aucuns disent que c'est l'algorithme le plus utilisé au monde !

Applet Java réalisée par David Eck , adaptée en français par Tahia Benhaj-Abdellatif.

Si l'applet ne s'affiche pas correctement

Face à un exemple de taille faible, il peut sembler quelque peu dérisoire de pousser le raffinement jusqu'à trouver un algorithme de tri supplémentaire à appliquer sur un petit nombre d'éléments, car la différence de complexité y sera peu visible ; cependant, il faut garder en mémoire qu'on peut vouloir trier des centaines de milliers d'éléments et que si une différence de stratégie est visible sur de petits nombres tels que 52 ou 200, a fortiori sur de grands ensembles la différence de complexité sera d'autant plus sensible.

On peut illustrer le cas général en prenant l'exemple du tri d'entiers. C'est ce que présente l'applet ci-dessus. Les différentes méthodes sont tout d'abord montrées, sous forme de Tri visuel, appliquées au tri de 16 éléments. Un deuxième niveau, appelé Tri temporel, permet de tester les différents algorithmes en choisissant un grand nombre d'éléments. Enfin, le menu Log garde la trace des essais successifs, afin de pouvoir les comparer.

Pour en savoir plus sur les différentes méthodes de tri

Pour décrire plus précisément les différentes méthodes de tri, leur procédure, leur complexité, on suppose qu'on dispose d'un tableau tab de N entiers numérotés de 1 à N et qu'on cherche à trier les entiers dans l'ordre croissant, « de gauche à droite » si on veut donner une représentation du tableau. On écrira les procédures de tri avec un « pseudo-code français » qui devrait être suffisamment clair pour ne pas nécessiter de traduction des mots clés. Mais ce « pseudo-code » est aussi suffisamment proche d'un langage informatique pour qu'un informaticien puisse aisément le transcrire dans un langage de programmation existant comme Java (le code utilisé dans l'applet) ou C++.

Afin d'évaluer la complexité des différents algorithmes de tri présentés, on comptera le nombre de comparaisons et d'échanges de valeur entre deux éléments du tableau sans prendre en compte les affectations et comparaisons sur des variables de comptage de boucles.

Les méthodes présentées sont de deux types :

• des méthodes qui trient les éléments deux à deux, de manière plus ou moins efficace, mais qui nécessitent toujours de comparer chacun des N éléments avec chacun des N-1 autres éléments, donc le nombre de comparaisons sera de l'ordre de N² - on note cet ordre de grandeur O(N²). Par exemple, pour N=1000, N²=10⁶, pour N=10⁶, N²=10¹². Les algorithmes de ce type sont :
  • une méthode de tri élémentaire, le tri par sélection ;
  • et sa variante, le tri par propagation ou tri bulle ;
  • une méthode qui s'apparente à celle utilisée pour trier ses cartes dans un jeu, le tri par insertion ;
• des méthodes qui sont plus rapides, car elles trient des sous-ensembles de ces N éléments puis regroupent les éléments triés, elles illustrent le principe « diviser pour régner ». Le nombre de comparaisons est alors de l'ordre de N (log(N)). Par exemple, pour N=1000, N(log(N))=10000 environ, pour N=10⁶, N(log(N))=20x10⁶ environ. Les algorithmes de ce type sont :
  • le fameux tri rapide ou Quicksort ;
  • et enfin, le tri par fusion .

Cette liste n'est évidemment pas exhaustive. Il existe des méthodes particulièrement adaptées à certains types de données spécifiques. Le tri par base (radix sort) en est un exemple.