Algorithmes de tri



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.

Suivant







































 

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)