Algorithmes de tri — comparaison du tri à bulles, du tri fusion et du tri rapide

Un algorithme de tri réorganise les mêmes éléments dans un certain ordre, par exemple du plus petit au plus grand. Si vous voulez la réponse courte d’abord, le tri à bulles est simple mais généralement trop lent pour les grandes listes, le tri fusion offre des performances fiables en $O(n \log n)$, et le tri rapide est souvent rapide en pratique lorsque ses partitions restent raisonnablement équilibrées.

La bonne question n’est pas « quel tri est le meilleur ? », mais « meilleur dans quelle situation ? ». Le tri à bulles illustre les échanges locaux, le tri fusion montre clairement l’approche diviser pour régner, et le tri rapide montre pourquoi la vitesse en moyenne peut être élevée même sans garantie sur le pire cas.

À quoi servent les algorithmes de tri

Étant donnée une liste comme $[5, 1, 4, 2]$, l’algorithme doit renvoyer les mêmes valeurs dans l’ordre :

$$[1, 2, 4, 5]$$

Cela paraît simple, mais différents algorithmes atteignent ce résultat de façons très différentes. Les principales différences sont :

• la manière dont ils déplacent les éléments
• le nombre de comparaisons ou d’échanges qu’ils utilisent en général
• la quantité de mémoire supplémentaire dont ils ont besoin
• leur sensibilité à de mauvais types d’entrées

Tri à bulles : échanges répétés entre voisins

Le tri à bulles parcourt la liste et échange les éléments adjacents qui ne sont pas dans le bon ordre. Après un passage complet, le plus grand élément encore non trié est « remonté » jusqu’à la fin.

Sur $[5, 1, 4, 2]$, le premier passage ressemble à ceci :

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Puis il recommence sur la partie restante non triée jusqu’à ce qu’aucun échange ne soit nécessaire.

Le tri à bulles est surtout utile pour apprendre. En général, sa complexité temporelle est en $O(n^2)$, donc le nombre de comparaisons augmente vite quand la liste grandit. Pour de petits exemples en classe, cela convient. Pour un vrai travail de tri, ce n’est généralement pas le bon choix.

Tri fusion : diviser, trier, puis fusionner

Le tri fusion utilise une idée de type diviser pour régner. Il découpe la liste en parties plus petites, trie ces parties, puis fusionne les morceaux triés.

Pour $[5, 1, 4, 2]$, on peut le voir simplement ainsi :

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

On trie chaque moitié :

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Puis on fusionne les deux moitiés triées :

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

La principale force du tri fusion est sa prévisibilité. Son temps d’exécution est en $O(n \log n)$ dans l’analyse habituelle, et pas seulement en moyenne. Son principal coût est la mémoire : les implémentations courantes sur tableaux utilisent de l’espace supplémentaire pendant la fusion.

Tri rapide : partitionner autour d’un pivot

Le tri rapide utilise lui aussi l’approche diviser pour régner, mais d’une autre manière. Il choisit un pivot, place les éléments plus petits d’un côté et les plus grands de l’autre, puis trie récursivement les deux côtés.

En utilisant le pivot $4$ sur $[5, 1, 4, 2]$, une partition possible est :

$$[1, 2] \;|\; 4 \;|\; [5]$$

Les parties de gauche et de droite sont alors beaucoup plus petites, donc le tri se termine rapidement.

Le tri rapide est souvent rapide en pratique parce que beaucoup d’implémentations partitionnent sur place et réduisent vite le problème lorsque le pivot coupe la liste de façon assez équilibrée. Mais cette condition compte. Si les choix de pivot sont souvent mauvais, par exemple en produisant encore et encore un côté minuscule et un côté presque complet, le pire cas devient $O(n^2)$.

Tri à bulles vs tri fusion vs tri rapide

Algorithme	Idée centrale	Temps typique	Temps dans le pire cas	Mémoire supplémentaire
Tri à bulles	Échanges répétés entre éléments adjacents	$O(n^2)$	$O(n^2)$	Faible
Tri fusion	Diviser, trier les moitiés, fusionner	$O(n \log n)$	$O(n \log n)$	Plus élevée dans les implémentations courantes sur tableaux
Tri rapide	Partitionner autour d’un pivot	Souvent $O(n \log n)$	$O(n^2)$	Souvent plus faible que le tri fusion

Si vous voulez retenir une idée pratique, c’est celle-ci : le tri à bulles est un algorithme d’apprentissage, le tri fusion est l’option stable et prévisible, et le tri rapide est souvent le choix le plus rapide en pratique quand l’implémentation gère bien les pivots.

Un exemple détaillé sur la même liste

Prenons la même liste :

$$[5, 1, 4, 2]$$

Le tri à bulles corrige sans cesse des erreurs locales. Il ne « voit » pas toute la structure, donc il peut avoir besoin de nombreux passages.

Le tri fusion commence par découper le problème en petits morceaux déjà triés, puis les combine. C’est cette structure qui explique pourquoi ses performances restent fiables quand la liste s’agrandit.

Le tri rapide essaie de faire très tôt une bonne séparation. Si cette séparation est assez équilibrée, le travail restant diminue vite.

C’est pour cela que les étudiants retiennent souvent mieux les nombres de complexité après avoir vu une même liste passer par chaque méthode. Ces nombres ne sont pas des étiquettes arbitraires. Ils reflètent la manière dont l’algorithme réduit le désordre.

Erreurs fréquentes quand on compare des algorithmes de tri

Supposer que le tri rapide est toujours plus rapide

Le tri rapide est souvent rapide en pratique, mais il n’est pas garanti d’être le plus rapide dans tous les cas. Un mauvais choix de pivot peut fortement le pénaliser.

Considérer tous les algorithmes en $O(n \log n)$ comme identiques

Le tri fusion et le tri rapide peuvent avoir le même taux de croissance moyen sans se comporter de la même façon en mémoire, en garanties sur le pire cas ou en détails d’implémentation.

Utiliser le tri à bulles parce qu’il est facile à coder

La facilité de codage n’est pas la même chose que l’adéquation au problème. Pour de toutes petites démonstrations, le tri à bulles convient. Pour des entrées réelles plus grandes, il effectue généralement du travail inutile.

Oublier le modèle d’entrée

Ces comparaisons supposent généralement un tri par comparaison sur des entrées générales. Si les données ont une structure particulière, des tris sans comparaison comme le tri par comptage peuvent changer complètement le choix.

Quand utilise-t-on chaque algorithme de tri ?

Le tri à bulles est surtout utilisé pour l’enseignement, le suivi pas à pas et de très petits exemples où la clarté compte plus que les performances.

Le tri fusion est utilisé quand un comportement régulier en $O(n \log n)$ est important et que l’usage de mémoire supplémentaire est acceptable. C’est aussi un choix naturel pour les listes chaînées et pour les situations où la stabilité du tri compte, selon l’implémentation.

Le tri rapide est utilisé quand la vitesse pratique est importante et que l’implémentation dispose d’une bonne stratégie de pivot ou de mécanismes de secours. Beaucoup de stratégies de tri des bibliothèques standard utilisent des idées du tri rapide avec des protections, plutôt qu’une version naïve de manuel.

Une façon rapide de retenir la différence

Retenez-les par leur mouvement :

• le tri à bulles corrige les voisins
• le tri fusion construit des moitiés triées
• le tri rapide sépare autour d’un pivot

Cette image mentale est plus utile que de mémoriser trois noms et trois formules.

Essayez votre propre version

Prenez la liste $[7, 3, 6, 1]$ et suivez un passage du tri à bulles, un cycle de division-fusion du tri fusion, et une partition autour d’un pivot pour le tri rapide. Si vous pouvez expliquer pourquoi la liste change différemment dans chaque cas, alors le concept est acquis.