Imaginez un jeu de 52 cartes mélangé que vous voulez trier de l'As au Roi. Quelle est votre stratégie ? Vous avez probablement une intuition — rendons-la précise, puis voyons si on peut faire mieux.
L'idée la plus simple : le tri à bulles
L'approche la plus évidente : parcourir la liste de gauche à droite. Dès que deux éléments adjacents sont dans le mauvais ordre, on les échange. On répète ce parcours jusqu'à ce qu'aucun échange ne soit nécessaire.
On appelle ça le tri à bulles parce que les petites valeurs « remontent » progressivement vers le début — comme des bulles dans l'eau.
Comptez les comparaisons. Pour 20 éléments, le tri à bulles effectue jusqu'à
190 comparaisons. C'est environ n²/2.
Les informaticiens écrivent ça O(n²) — « ordre n carré ».
Doubler les données → quatre fois plus de travail.
Peut-on faire mieux ?
Oui — et de façon spectaculaire. Le problème du tri à bulles, c'est qu'il compare des éléments adjacents, donc un petit nombre tout à droite met beaucoup de passages pour remonter à gauche.
Le tri fusion adopte une approche radicalement différente :
diviser la liste en deux, trier chaque moitié, puis fusionner.
C'est ce qu'on appelle diviser pour régner — et ça s'exécute en
O(n log n) au lieu de O(n²).
À quoi ressemble cette différence en pratique ? Regardons-les s'affronter.
Pour 100 éléments : le tri à bulles effectue ~5 000 opérations. Le tri fusion en fait ~700. C'est un gain de 7×. Pour 1 000 éléments, l'écart passe à 50×. C'est pourquoi l'efficacité algorithmique compte à grande échelle.
Ce qu'il faut retenir
La notation Big-O (O(n²), O(n log n)) n'est pas
qu'une abstraction mathématique — c'est une prédiction du comportement d'un
algorithme quand les données grandissent. Un algorithme plus rapide
sur 10 éléments peut être négligeable. Sur un million, c'est la différence
entre instantané et inutilisable.
Les fonctions de tri intégrées dans la plupart des langages utilisent des variantes du tri fusion ou un hybride appelé Timsort — parce que l'avantage théorique est bien réel en pratique.