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