Le tri à bulles, ou bubble sort, est l’un des algorithmes de tri les plus faciles à comprendre. Il parcourt une liste, compare les éléments voisins, puis échange ceux qui ne sont pas dans le bon ordre. À chaque passage, les grandes valeurs “remontent” progressivement vers la fin de la liste, comme des bulles.
En Python, on peut l’implémenter en quelques lignes.
def tri_a_bulles(valeurs):
valeurs = valeurs.copy()
n = len(valeurs)
for i in range(n):
for j in range(0, n - i - 1):
if valeurs[j] > valeurs[j + 1]:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
return valeurs
print(tri_a_bulles([5, 1, 4, 2, 8]))
Résultat :
[1, 2, 4, 5, 8]
En pratique, pour trier une liste dans un vrai programme Python, utilisez plutôt sorted() ou list.sort(). Le tri à bulles est surtout utile pour apprendre les boucles, les comparaisons, les échanges et la complexité algorithmique.
La réponse courte
Le tri à bulles répète cette règle :
si deux éléments voisins sont dans le mauvais ordre, on les échange
Après un passage complet, le plus grand élément restant est placé à sa position finale. On répète jusqu’à ce que la liste soit triée.
Version simple :
def tri_a_bulles(valeurs):
valeurs = valeurs.copy()
for i in range(len(valeurs)):
for j in range(len(valeurs) - i - 1):
if valeurs[j] > valeurs[j + 1]:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
return valeurs
Complexité :
| Cas | Temps |
|---|---|
| Meilleur cas avec optimisation | O(n) |
| Cas moyen | O(n²) |
| Pire cas | O(n²) |
| Mémoire supplémentaire | O(1) hors copie |
Sans optimisation, même une liste déjà triée reste parcourue inutilement.
Comment fonctionne le tri à bulles
Prenons cette liste :
[5, 1, 4, 2, 8]
Premier passage :
[5, 1, 4, 2, 8] -> échange 5 et 1
[1, 5, 4, 2, 8] -> échange 5 et 4
[1, 4, 5, 2, 8] -> échange 5 et 2
[1, 4, 2, 5, 8] -> 5 et 8 sont dans le bon ordre
À la fin du passage, 8 est déjà au bon endroit. Au passage suivant, il est inutile de le comparer à nouveau.
C’est pour cela que la boucle interne s’arrête à :
len(valeurs) - i - 1
À chaque passage, une valeur supplémentaire est fixée à la fin.
Version optimisée avec arrêt anticipé
Si la liste est déjà triée, le tri à bulles peut s’arrêter après un seul passage. Il suffit de vérifier si un échange a eu lieu.
def tri_a_bulles_optimise(valeurs):
valeurs = valeurs.copy()
n = len(valeurs)
for i in range(n):
echange = False
for j in range(0, n - i - 1):
if valeurs[j] > valeurs[j + 1]:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
echange = True
if not echange:
break
return valeurs
Test :
print(tri_a_bulles_optimise([1, 2, 3, 4, 5]))
print(tri_a_bulles_optimise([5, 4, 3, 2, 1]))
Résultat :
[1, 2, 3, 4, 5]
[1, 2, 3, 4, 5]
Cette optimisation change le meilleur cas : une liste déjà triée passe de O(n²) à O(n).
Trier en place ou renvoyer une copie
Deux styles sont possibles.
Version qui renvoie une nouvelle liste :
def tri_a_bulles(valeurs):
valeurs = valeurs.copy()
# tri...
return valeurs
Version qui modifie directement la liste :
def tri_a_bulles_en_place(valeurs):
n = len(valeurs)
for i in range(n):
echange = False
for j in range(0, n - i - 1):
if valeurs[j] > valeurs[j + 1]:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
echange = True
if not echange:
break
Utilisation :
nombres = [5, 1, 4, 2, 8]
tri_a_bulles_en_place(nombres)
print(nombres)
La version en place économise une copie, mais elle modifie la liste donnée. Pour un tutoriel, renvoyer une copie est souvent plus sûr.
Pourquoi le tri à bulles est en O(n²)
Avec n éléments, le premier passage fait environ n - 1 comparaisons. Le deuxième en fait n - 2, puis n - 3, etc.
Le total ressemble à :
(n - 1) + (n - 2) + ... + 1
Ce qui donne environ :
n² / 2
En notation Big O, on ignore les constantes :
O(n²)
Cette complexité explique pourquoi le tri à bulles devient vite lent quand la liste grandit. Pour 100 éléments, ce n’est pas grave. Pour 100 000 éléments, c’est une mauvaise idée.
Pour approfondir cette notion, voir la complexité algorithmique en Python.
Compter les comparaisons et les échanges
Pour comprendre le coût réel, on peut instrumenter l’algorithme.
def tri_a_bulles_stats(valeurs):
valeurs = valeurs.copy()
comparaisons = 0
echanges = 0
n = len(valeurs)
for i in range(n):
echange = False
for j in range(0, n - i - 1):
comparaisons += 1
if valeurs[j] > valeurs[j + 1]:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
echanges += 1
echange = True
if not echange:
break
return valeurs, comparaisons, echanges
Exemple :
resultat, comparaisons, echanges = tri_a_bulles_stats([5, 1, 4, 2, 8])
print(resultat)
print(comparaisons)
print(echanges)
Ce genre de mesure aide à comprendre pourquoi certains algorithmes simples sont pédagogiques mais pas performants.
Trier des objets avec une clé
Le tri à bulles peut aussi trier des objets selon une clé, comme sorted().
def tri_a_bulles_key(valeurs, key=lambda x: x):
valeurs = valeurs.copy()
n = len(valeurs)
for i in range(n):
echange = False
for j in range(0, n - i - 1):
if key(valeurs[j]) > key(valeurs[j + 1]):
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
echange = True
if not echange:
break
return valeurs
Exemple :
personnes = [
{"nom": "Amina", "age": 31},
{"nom": "Yanis", "age": 24},
{"nom": "Lea", "age": 28},
]
print(tri_a_bulles_key(personnes, key=lambda p: p["age"]))
Dans un vrai projet, vous écririez plutôt :
sorted(personnes, key=lambda p: p["age"])
Mais l’exercice montre comment une fonction de comparaison peut être intégrée dans un algorithme.
Tri à bulles ou sorted()
Python fournit deux outils de tri à utiliser en priorité :
nouvelle_liste = sorted(valeurs)
et :
valeurs.sort()
sorted() renvoie une nouvelle liste. list.sort() trie la liste en place. Ces fonctions sont stables, très optimisées et beaucoup plus adaptées à la production que le tri à bulles.
Le tri à bulles reste intéressant pour apprendre :
- les boucles imbriquées ;
- les échanges de valeurs ;
- la notion de complexité ;
- le meilleur cas, le pire cas et l’arrêt anticipé ;
- la différence entre algorithme pédagogique et fonction de production.
Erreurs fréquentes
Oublier - 1 dans la boucle interne
Si vous écrivez :
for j in range(len(valeurs)):
if valeurs[j] > valeurs[j + 1]:
...
vous finirez par accéder à valeurs[j + 1] hors de la liste.
La boucle correcte doit s’arrêter avant le dernier index :
for j in range(0, n - i - 1):
Modifier la liste sans le vouloir
Si vous voulez garder la liste d’origine, faites une copie :
valeurs = valeurs.copy()
Sinon, votre fonction triera directement l’objet passé en argument.
Croire que le tri à bulles est efficace
Le tri à bulles est facile à lire, mais il est rarement efficace. Pour trier de vraies données, utilisez sorted() ou list.sort().
Confondre stable et efficace
Le tri à bulles est stable si l’on échange seulement quand valeurs[j] > valeurs[j + 1], et non quand les valeurs sont égales. Mais stable ne veut pas dire rapide.
Exercices rapides
Exercice 1
Que renvoie ce code ?
print(tri_a_bulles([3, 2, 1]))
Correction :
[1, 2, 3]
Exercice 2
Ajoutez un paramètre reverse=True pour trier dans l’ordre décroissant.
Correction possible :
def tri_a_bulles_reverse(valeurs, reverse=False):
valeurs = valeurs.copy()
n = len(valeurs)
for i in range(n):
echange = False
for j in range(0, n - i - 1):
mauvais_ordre = valeurs[j] > valeurs[j + 1]
if reverse:
mauvais_ordre = valeurs[j] < valeurs[j + 1]
if mauvais_ordre:
valeurs[j], valeurs[j + 1] = valeurs[j + 1], valeurs[j]
echange = True
if not echange:
break
return valeurs
Exercice 3
Comparez le nombre de comparaisons entre :
[1, 2, 3, 4, 5]
et :
[5, 4, 3, 2, 1]
avec la fonction tri_a_bulles_stats.
Pour aller plus loin
Le tri à bulles est un bon premier algorithme de tri, mais il ne doit pas rester le seul. Après lui, les tris par insertion, sélection, fusion et rapide permettent de comprendre des stratégies différentes.
À lire ensuite :
- Complexité algorithmique en Python : comprendre O(n), O(log n) et O(n²)
- Algorithmes de graphes en Python : le guide pour bien démarrer
- Modulo en Python : comprendre %, // et divmod avec exemples
La règle à retenir : le tri à bulles est excellent pour apprendre, mais sorted() et list.sort() sont les bons outils pour trier en production.
Références
- Documentation Python officielle : Sorting HOW TO
- Documentation Python officielle :
sorted() - Wikipedia : Bubble sort
