02 — Le tri à bulles, à connaître mais pas à utiliser
Ce que tu vas apprendre
- Le principe du tri à bulles et son nom
- Son implémentation, avec l'optimisation du drapeau
- Pourquoi il reste en O(n²) malgré l'optimisation
- Pourquoi on l'enseigne mais qu'on ne l'utilise pas
Prérequis
Le tri à bulles est le tri le plus enseigné au monde, et probablement le moins utilisé en production. Son intérêt est pédagogique : il illustre parfaitement ce qu'est un tri quadratique. Mais il n'a aucun cas d'usage réel où il battrait l'insertion. Le connaître sert surtout à reconnaître un anti-pattern quand on le croise dans du code existant.
Le principe
On parcourt le tableau et on compare chaque paire d'éléments adjacents. Si deux voisins sont dans le mauvais ordre, on les échange. Après une passe complète, le plus grand élément a « remonté » jusqu'à la fin, comme une bulle d'air remonte à la surface, d'où le nom. On répète jusqu'à ce qu'aucun échange ne soit nécessaire.
typescriptfunction triBulle(arr: number[]): number[] {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; // échange de voisins
}
}
}
return arr;
}
À chaque passe externe, le plus grand élément non encore placé migre vers sa position finale. Le - i dans la boucle interne évite de recomparer la partie déjà triée en fin de tableau.
L'optimisation du drapeau
Une amélioration courante : si une passe complète ne provoque aucun échange, c'est que le tableau est déjà trié, on peut s'arrêter. On ajoute un drapeau booléen.
pythondef tri_bulle(arr: list[int]) -> list[int]:
n = len(arr)
for i in range(n - 1):
echange = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
echange = True
if not echange: # aucune permutation : c'est trié
break
return arr
Avec ce drapeau, le meilleur cas (tableau déjà trié) devient O(n) : une seule passe sans échange, puis arrêt. Le tri à bulles rejoint l'insertion sur ce point précis.
Pourquoi il reste à éviter
Malgré l'optimisation, le cas moyen et le pire cas restent en O(n²). Et même à complexité égale avec le tri par insertion, le tri à bulles est plus lent en pratique : il fait beaucoup plus d'échanges. Là où l'insertion décale les éléments une fois trouvée la bonne position, le tri à bulles échange à répétition des voisins, ce qui multiplie les écritures en mémoire.
| Tri | Meilleur cas | Cas moyen | Pire cas | Échanges | Stable |
|---|---|---|---|---|---|
| Bulle (avec drapeau) | O(n) | O(n²) | O(n²) | beaucoup | oui |
| Insertion | O(n) | O(n²) | O(n²) | peu | oui |
Le tri à bulles est stable (on n'échange que des éléments strictement désordonnés) et en place. Mais ces qualités, l'insertion les a aussi, en faisant moins de travail. Il n'existe donc aucune situation où le tri à bulles est le bon choix. C'est l'exemple parfait d'un algorithme correct mais dominé : il fait le job, mais quelque chose fait toujours mieux.
Ce qu'il faut en retenir
Le tri à bulles mérite d'être compris parce qu'il est partout dans les cours et qu'on le rencontre parfois dans du vieux code. Quand tu le vois, c'est souvent le signe que quelqu'un a implémenté un tri à la main sans connaître les alternatives. Le réflexe : remplacer par le sort() du langage, ou par une insertion si tu dois vraiment trier toi-même de petits tableaux.
Les trois premiers tris de cette série étaient tous en O(n²). L'article suivant change de catégorie : le tri par fusion atteint O(n log n), grâce à la stratégie diviser pour régner.
Sources
- Videau, M., & Eck, D. (2004). Les algorithmes de tri. Interstices. interstices.info/les-algorithmes-de-tri/ (Le tri à bulles y est nommé « tri par propagation »)
- Astrachan, O. (2003). Bubble Sort: An Archaeological Algorithmic Analysis. ACM SIGCSE Bulletin, 35(1). (Pourquoi on continue d'enseigner un tri qu'on déconseille)
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Problème 2-2. MIT Press.