Comment ça marche
Trier, c’est ranger des éléments en ordre — du plus petit au plus grand, de A à Z. Tous les algorithmes ci-dessous résolvent le même problème ; ils ne diffèrent que par la stratégie, et c’est la stratégie que vous regardez. Choisissez un algorithme (ou le mode course pour les six à la fois), choisissez une entrée et appuyez sur lecture. Les barres s’illuminent pendant que le moteur travaille : lejaune marque une comparaison, le rouge un déplacement ou un échange, leviolet le pivot et le vert les positions terminées.
Les commandes rappellent un lecteur vidéo parce que le moteur en est un : lecture et pause avec la barre d’espace, un pas à la fois avec la flèche droite, recommencer avec R, nouvelle liste avecN, mélanger avec S et vitesses de 0,25× à 8×. Un panneau de code surligne chaque ligne du pseudocode pendant son exécution, pour que l’animation et le programme avancent ensemble. Essayez la même course deux fois : une fois sur une liste inversée, une fois presque triée, et regardez le tri par insertion passer de la queue du peloton à la tête.
Les six algorithmes
Trois sont des méthodes quadratiques simples — faciles à écrire, douloureuses à grande échelle. Trois sont des méthodes efficaces qui atteignent O(n log n) par diviser-pour-régner ou une structure de données astucieuse. Chaque exemple ci-dessous est du Python complet et exécutable, sur une liste ordinaire.
Tri à bulles — l’échange de voisins
Parcourez la liste en comparant les voisins et en échangeant les paires désordonnées. À chaque passage, le plus grand élément non trié « remonte » à sa place finale, donc le passage suivant peut être un peu plus court. Si un passage complet ne fait aucun échange, la liste est déjà triée et l’algorithme s’arrête tôt — sa seule qualité rédemptrice, qui donne O(n) sur les entrées déjà triées.
def bubble_sort(a):
n = len(a)
for end in range(n - 1, 0, -1):
swapped = False
for i in range(end):
if a[i] > a[i + 1]:
a[i], a[i + 1] = a[i + 1], a[i]
swapped = True
if not swapped:
break
return aTri par sélection — prendre le plus petit, répéter
Divisez la liste en début trié et reste non trié. À chaque étape, balayez tout le reste à la recherche de son minimum et échangez-le à sa place. Il fait toujours le même nombre de comparaisons — environ n²/2 — aussi triée que soit déjà l’entrée ; c’est pourquoi ses cas meilleur, moyen et pire sont tous O(n²). Sa vertu est de faire au plus n échanges, utile quand échanger coûtait cher.
def selection_sort(a):
n = len(a)
for i in range(n):
m = i
for j in range(i + 1, n):
if a[j] < a[m]:
m = j
a[i], a[m] = a[m], a[i]
return aTri par insertion — la méthode du joueur de cartes
Comme on trie ses cartes en main : prenez l’élément suivant et glissez-le vers la gauche devant tout ce qui est plus grand, jusqu’à sa place. Sur des données presque triées, presque rien ne bouge, donc il tourne en O(n) — le plus rapide de la salle dans ce cas, et la raison pour laquelle les vrais tris hybrides l’emploient sur les petites sous-listes. Sur des données inversées, chaque élément parcourt toute la distance : pire cas O(n²). Il est stable et n’utilise pas de mémoire supplémentaire.
def insertion_sort(a):
for i in range(1, len(a)):
key = a[i]
j = i - 1
while j >= 0 and a[j] > key:
a[j + 1] = a[j]
j -= 1
a[j + 1] = key
return aTri fusion — diviser, régner, fusionner
Coupez la liste en deux, triez chaque moitié pareil (la récursion atteint des éléments uniques, triés par définition) puis fusionnez les moitiés en prenant toujours le plus petit des deux fronts. La coupe est toujours équilibrée, donc chaque niveau coûte O(n) et il y a log n niveaux : O(n log n) garanti, dans tous les cas. Le prix est O(n) de mémoire supplémentaire pour fusionner, et il est stable — les éléments égaux ne se croisent jamais.
def merge_sort(a):
if len(a) <= 1:
return a
mid = len(a) // 2
left = merge_sort(a[:mid])
right = merge_sort(a[mid:])
out, i, j = [], 0, 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
out.append(left[i]); i += 1
else:
out.append(right[j]); j += 1
return out + left[i:] + right[j:]Tri rapide — partition autour d’un pivot
Choisissez un pivot, puis partitionnez : tout ce qui est plus petit va à gauche, tout ce qui est plus grand à droite. Triez chaque côté pareil. Quand les pivots tombent près du milieu, la récursion fait log n niveaux et le total est O(n log n) avec de minuscules constantes et seulement O(log n) de mémoire supplémentaire pour la récursion — en général le plus rapide en pratique. Quand ils tombent à une extrémité, un côté garde presque tout et il se dégrade en O(n²). Ce simulateur choisit ses pivots par médiane de trois (premier, milieu et dernier éléments), ce qui rend le mauvais cas rare sur les données réelles. L’exemple Python ci-dessous prend simplement le dernier élément comme pivot, pour rester court.
def quick_sort(a, lo=0, hi=None):
if hi is None:
hi = len(a) - 1
if lo < hi:
p, i = a[hi], lo
for j in range(lo, hi):
if a[j] < p:
a[i], a[j] = a[j], a[i]
i += 1
a[i], a[hi] = a[hi], a[i]
quick_sort(a, lo, i - 1)
quick_sort(a, i + 1, hi)
return aTri par tas — une file de priorité déguisée
Transformez la liste en tas-max : un arbre binaire tassé dans le tableau où chaque parent est plus grand que ses enfants, donc le maximum est à la position zéro. Retirez le maximum à répétition, échangez-le à la fin, rétrécissez le tas d’un cran et restaurez la propriété en faisant descendre le nouveau sommet. O(n log n) garanti avec O(1) de mémoire supplémentaire — mais l’accès sautillant déplaît aux caches du processeur, donc il perd souvent contre les tris rapide et fusion au chronomètre, malgré l’égalité sur le papier.
def heap_sort(a):
def sift(lo, n, i):
while True:
l, r, m = 2 * i + 1, 2 * i + 2, i
if l < n and a[lo + l] > a[lo + m]:
m = l
if r < n and a[lo + r] > a[lo + m]:
m = r
if m == i:
return
a[lo + i], a[lo + m] = a[lo + m], a[lo + i]
i = m
n = len(a)
for i in range(n // 2 - 1, -1, -1):
sift(0, n, i)
for end in range(n - 1, 0, -1):
a[0], a[end] = a[end], a[0]
sift(0, end, 0)
return aLire le tableau
Big-O décrit la croissance, pas le chronomètre : constantes et matériel sont ignorés exprès pour que laforme de l’échelle apparaisse. Le tableau ci-dessous est la référence standard (Cormen et al.,Introduction to Algorithms ; Dictionnaire des algorithmes et structures de données du NIST). « Stable » signifie que les éléments égaux gardent leur ordre d’origine.
| Algorithme | Meilleur | Moyen | Pire | Mémoire suppl. | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | Oui |
| Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | Non |
| Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | Oui |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Oui |
| Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | Non |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | Non |
Essayez dans le simulateur : lancez les six sur une liste inversée, puis sur une liste presque triée. L’ordre d’arrivée s’inverse — le tri par insertion passe de la queue du peloton à la tête — et aucune formule ne l’enseigne comme le voir arriver.
Trois erreurs fréquentes
« Le tri rapide est toujours le plus rapide. » En moyenne, il compte parmi les plus rapides, mais un tri rapide simple a un pire cas en O(n²), par exemple quand le pivot tombe toujours à une extrémité de la liste. Le tri fusion et le tri par tas restent en O(n log n) quelle que soit l’entrée.
« Les méthodes quadratiques simples ne servent à rien. » Le tri par insertion est très utilisé pour les petites listes et se comporte très bien sur les listes presque triées. Les routines de tri utilisées en pratique sont généralement hybrides et passent au tri par insertion pour les petits morceaux.
« Un tri stable est un tri qui n’échoue jamais. » La stabilité a un sens précis : les éléments de même clé conservent l’ordre qu’ils avaient avant le tri. Le tri fusion et le tri par insertion sont stables ; le tri rapide et le tri par tas, sous leur forme habituelle, ne le sont pas.
Questions des visiteurs
Quel algorithme de tri utiliser dans du vrai code ?
Presque toujours le tri natif du langage : sorted() en Python, Array.sort() en JavaScript ou Arrays.sort() en Java pour les objets. Ce sont des hybrides d’ingénierie (Python et Java utilisent Timsort) en temps O(n log n), stables et testés par des millions d’utilisateurs. Les six algorithmes de cette page enseignent les idées derrière ces outils, ils ne les remplacent pas.
Si le tri à bulles est lent, pourquoi l’enseigne-t-on encore ?
Parce que c’est l’idée de tri la plus simple possible : comparer les voisins, échanger s’ils sont désordonnés, répéter. Le voir peiner face au tri fusion dans le mode course enseigne plus sur la croissance O(n²) que n’importe quelle formule. L’arrêt anticipé montre aussi que le même algorithme peut être O(n) sur une entrée déjà triée et O(n²) en général.
Que signifie qu’un tri est stable ?
Un tri stable conserve les éléments égaux dans leur ordre relatif d’origine. C’est important pour trier sur plusieurs clés : triez une classe par nom puis par note avec un algorithme stable, et les élèves à égalité restent par ordre alphabétique. Les tris fusion, insertion et à bulles sont stables ; les tris sélection, rapide et par tas, tels qu’on les implémente normalement, ne le sont pas.
Pourquoi le tri rapide n’est-il pas toujours le plus rapide s’il est O(n log n) en moyenne ?
Parce que son pire cas est O(n²) : avec des pivots malchanceux, chaque partition n’isole qu’un élément. Les bonnes implémentations l’évitent par pivot médiane de trois (comme dans ce simulateur) ou randomisation. Le tri fusion garantit O(n log n) mais utilise O(n) de mémoire supplémentaire ; le tri par tas garantit O(n log n) en place, mais saute en mémoire, ce que les caches modernes n’aiment pas.
Le simulateur exécute-t-il vraiment les algorithmes, ou est-ce une animation ?
Il les exécute vraiment. Chaque algorithme fait tourner sa logique authentique et émet des événements — comparaison, échange, écrasement, pivot, fusion, entassement — que le graphique animé rejoue. En mode course, les six tournent sur la même entrée côte à côte, donc la comparaison est équitable. Le mode mots trie le texte sans tenir compte des accents ni de la casse.
Que compte vraiment la notation Big-O ?
Comment le nombre d’opérations de base grandit avec l’entrée, en ignorant les facteurs constants. O(n²) signifie que doubler l’entrée quadruple presque le travail ; O(n log n) signifie que doubler ne fait guère plus que doubler. Avec n = 1 000 000, c’est la différence entre environ un billion d’opérations et vingt millions — des minutes, voire des heures, contre une fraction de seconde.
Sources et lectures complémentaires
- Introduction to Algorithms — MIT Press (Cormen et al.)
- Sorting algorithm — Wikipedia
- Dictionary of Algorithms and Data Structures — NIST
- Algorithms course — Khan Academy
Citer cette exposition
Eurekarium. (2026). Laboratoire de tri. https://eurekarium.com/fr/computing/sorting-lab/
Dernière mise à jour :