Tri à bulles, par insertion, par fusion, rapide et par tas sur une même permutation — cinq rangées de barres avancent ensemble.
À propos du modèle
Les algorithmes de tri comparés ici travaillent sur une même permutation des entiers 1…n : tri à bulles (échange de voisins), tri par insertion (recul de la clé), tri par fusion de bas en haut (passes de largeur doublée), tri rapide avec partition de Lomuto et pile explicite d’intervalles, tri par tas (construction d’un tas max et tamisage à l’extraction). Un même micropas fait avancer les cinq à la fois : on voit des tableaux de permutations différents, et non une course au temps processeur — les méthodes n’ont pas le même nombre de pas. Les barres sont colorées selon l’indice d’origine ; le surlignage marque la comparaison ou l’échange en cours. C’est une animation pédagogique des comparaisons et des échanges, pas une mesure de complexité réelle sur une machine donnée.
Public : Cours d’informatique d’introduction : comparaison des familles O(n²) et O(n log n) sur une même permutation.
Notions clés
tri à bulles
tri par insertion
tri par fusion
tri rapide
tri par tas
partition de Lomuto
tas binaire
stabilité d’un tri
Comment ça marche
Une permutation 1…n, cinq tris. Chaque micropas — comparaison ou échange — s’exécute dans toutes les rangées à la fois, donc on voit comment le tableau se réordonne autrement pour le tri à bulles, par insertion, par fusion de bas en haut, le tri rapide (Lomuto) et le tri par tas, et non seulement qui est plus rapide à l’horloge.
Questions fréquentes
Pourquoi les rangées se terminent-elles à des instants différents ?
Sur une même entrée, les algorithmes n’ont pas le même nombre de comparaisons et d’échanges. Le pas commun reste un pour les cinq : les rangées déjà triées attendent que les plus « longues » en nombre d’opérations les rattrapent.
Le tri par fusion est-il stable ici ?
En cas de clés égales, la fusion prend l’élément de la moitié gauche (condition ≤) — implémentation stable habituelle. Les autres méthodes montrées ne garantissent pas la stabilité en général.
Pourquoi le tri rapide paraît-il plus « bruyant » que le tri par tas ?
La partition de Lomuto parcourt le sous-tableau et fait beaucoup d’échanges autour du pivot ; dans le tri par tas, le travail principal est le tamisage le long d’un chemin de l’arbre. L’ordre O(n log n) est typique des deux, mais les constantes et le motif de déplacement diffèrent.