On désigne par "tri" l'opération consistant à ordonner un ensemble d'éléments en fonction de clés sur lesquelles est définie une relation d'ordre.
Les algorithmes de tri ont une grande importance pratique. Ils sont fondamentaux dans certains domaines, comme l'informatique de gestion où l'on tri de manière quasi-systématique des données avant de les utiliser.
L'étude du tri est également intéressante en elle-même car il s'agit sans doute du domaine de l'algorithmique qui a été le plus étudié et qui a conduit à des résultats remarquables sur la construction d'algorithmes et l'étude de leur complexité.
Pour vous donner une idée de la difficulté du problème, je vous propose le petit jeu suivant. Il s'agit de trier quelques tonneaux (entre 3 et 10) par ordre de poids croissant. Le poids de chaque tonneau a été attribué aléatoirement. Utilisez le "glisser-déposer" pour déplacer les tonneaux.
Vous ne disposez que d'une balance non étalonnée vous permettant de comparer le poids des tonneaux 2 à 2 et d'étagères pouvant vous servir de stockage intermédiaire.
Ce sont exactement les mêmes éléments que ceux dont dispose un ordinateur : une fonction de comparaison et des zones de stockage.
Le but du jeu est évidemment de trier ces tonneaux en faisant le moins de comparaisons et d'échanges possibles.
Les pages suivantes présentent les principaux algorithmes de tri :
Tris stables | Tris non stables |
| Le tri par insertion. | Le tri par sélection. |
| Le tri bulle. | Le tri à peigne. |
| Le tri Shaker. | Le tri Shell. |
| Le tri Gnome. | Le tri maximier. |
| Le tri fusion. | Le tri rapide. |
La petite démo ci-dessous compte, pour quelques un des principaux algorithmes de tri, le nombre de comparaisons et le nombre d'échanges.
| Algorithme | Complexite | Stabilité | Nombre de comparaisons | Nombre d'échanges | Démo | ||
|---|---|---|---|---|---|---|---|
| Pire | Moyen | Meilleur | |||||
| Tri par insertion (Insertion Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri par sélection ou tri par extraction (Selection Sort) | Θ(n2) | Θ(n2) | Θ(n2) | Non | |||
| Tri bulle ou tri par propagation (Bubble Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri shaker ou bidirectionnel (Cocktail Sort) | Θ(n2) | Θ(n2) | Θ(n) | Oui | |||
| Tri à peigne (Comb Sort) | |||||||
| Tri de Shell (Shell sort) | Non | ||||||
| Tri de Batcher (Batcher odd–even mergesort / Bitonic Sort) | |||||||
| Tri rapide (Quicksort) | |||||||
Vous trouverez ici un programme Javascript permettant de comparer les différents algorithmes de tri.