Les algorithmes de tri  (d'après le site interstices)

Selon le dictionnaire, « trier » signifie « répartir en plusieurs classes selon certains critères ». De manière plus restrictive, le terme de « tri » en algorithmique est très souvent attaché au processus de classement d'un ensemble d'éléments dans un ordre donné. Par exemple, trier N entiers dans l'ordre croissant, ou N noms dans l'ordre alphabétique. Tout ensemble muni d'un ordre total peut fournir une suite d'éléments à trier.

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é definition 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 document externe au site, adaptée en français par Tahia Benhaj-Abdellatif.


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 langage 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).

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 :

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 document externe au site (radix sort) en est un exemple.