Une liste de nombres désordonnée peut sembler anodine, mais elle permet de comprendre plusieurs mécanismes essentiels de la programmation. Le tri à bulles en Python montre concrètement comment comparer des valeurs, les échanger et réduire progressivement la partie encore non triée d’un tableau. Je présente ici son fonctionnement, une implémentation claire, sa version optimisée, ses limites et les situations où il vaut mieux choisir une autre méthode.
L’essentiel du tri à bulles en Python en quelques points
- Principe : comparer deux éléments voisins et les échanger s’ils sont dans le mauvais ordre.
- Résultat : le plus grand élément restant se déplace vers la fin à chaque passage.
- Complexité : O(n²) dans le cas moyen et défavorable, contre O(n) sur une liste déjà triée avec optimisation.
- Mémoire : le tri s’effectue directement dans la liste, avec un espace supplémentaire de O(1).
- Usage conseillé : apprendre les algorithmes, tester une logique d’échange ou traiter de très petites listes.
Comment fonctionne le tri à bulles
Le principe est simple. On parcourt la liste et on compare chaque élément avec celui qui le suit. Si le premier est plus grand que le second, on les échange. À la fin du passage, la plus grande valeur rencontrée a progressivement remonté jusqu’à la dernière position disponible.
Avec la liste [5, 2, 4, 1], le premier passage compare 5 et 2, puis 5 et 4, puis 5 et 1. Le nombre 5 finit à droite, car il est plus grand que tous les autres. Le passage suivant peut donc s’arrêter une position plus tôt.
J’aime utiliser cette image avec les débutants, car elle rend visible une idée importante en algorithmique : une partie de la liste devient définitivement correcte après chaque tour. L’algorithme ne mélange pas toutes les valeurs au hasard, il réduit progressivement le travail restant.
Une implémentation Python facile à comprendre
Voici une version classique qui trie une liste dans l’ordre croissant. Elle modifie la liste originale et ne renvoie rien explicitement.
def tri_bulles(liste):
n = len(liste)
for passage in range(n - 1):
for i in range(n - 1 - passage):
if liste[i] > liste[i + 1]:
liste[i], liste[i + 1] = liste[i + 1], liste[i]
nombres = [5, 2, 4, 1, 3]
tri_bulles(nombres)
print(nombres)
# [1, 2, 3, 4, 5]La variable passage compte les tours déjà effectués. La limite n - 1 - passage est importante, car les derniers éléments sont déjà placés. Il est inutile de les comparer à nouveau.
En Python, l’instruction liste[i], liste[i + 1] = liste[i + 1], liste[i] permet d’échanger deux valeurs sans variable temporaire. C’est une particularité pratique du langage, mais le mécanisme reste le même qu’en pseudo-code.
Lire aussi : chr() Python - Convertir un entier en caractère Unicode sans erreur
Une version qui renvoie une nouvelle liste
Modifier directement la liste n’est pas toujours souhaitable. Pour conserver les données originales, je préfère parfois travailler sur une copie et retourner le résultat.
def tri_bulles_copie(liste):
resultat = liste.copy()
n = len(resultat)
for passage in range(n - 1):
for i in range(n - 1 - passage):
if resultat[i] > resultat[i + 1]:
resultat[i], resultat[i + 1] = (
resultat[i + 1],
resultat[i]
)
return resultat
nombres = [5, 2, 4, 1, 3]
tries = tri_bulles_copie(nombres)
print(nombres) # [5, 2, 4, 1, 3]
print(tries) # [1, 2, 3, 4, 5]Cette variante consomme davantage de mémoire, puisque Python conserve deux listes. En contrepartie, elle évite une modification parfois surprenante pour le code qui utilise encore la liste de départ.
Optimiser l’algorithme avec un arrêt anticipé
La version précédente effectue tous les passages prévus, même si la liste est déjà triée avant la fin. On peut éviter ce travail en mémorisant si un échange a eu lieu pendant le passage.
def tri_bulles_optimise(liste):
n = len(liste)
for passage in range(n - 1):
echange = False
for i in range(n - 1 - passage):
if liste[i] > liste[i + 1]:
liste[i], liste[i + 1] = liste[i + 1], liste[i]
echange = True
if not echange:
break
nombres = [1, 2, 3, 4, 5]
tri_bulles_optimise(nombres)
print(nombres)
# [1, 2, 3, 4, 5]Si aucun échange n’est réalisé, toutes les paires voisines sont déjà dans le bon ordre. La liste est donc triée et la boucle peut s’arrêter. Dans le meilleur cas, une liste déjà ordonnée est parcourue une seule fois, ce qui donne une complexité de O(n).
Cette optimisation améliore le comportement sur des données presque triées, mais elle ne transforme pas l’algorithme en solution adaptée aux grandes listes. Avec une liste inversée, il reste proche de O(n²), car le nombre de comparaisons augmente très rapidement.
Complexité, stabilité et limites à connaître
La complexité décrit la manière dont le temps d’exécution évolue quand la taille de la liste augmente. Pour le tri à bulles, le cas moyen et le pire cas sont en O(n²). Une liste dix fois plus longue peut donc demander environ cent fois plus de comparaisons dans une situation défavorable.
| Aspect | Comportement |
|---|---|
| Meilleur cas | O(n) avec l’arrêt anticipé |
| Cas moyen | O(n²) |
| Pire cas | O(n²) |
| Mémoire supplémentaire | O(1) |
| Stabilité | Oui, si l’on échange uniquement les valeurs strictement supérieures |
Un tri est dit stable lorsqu’il conserve l’ordre de deux éléments ayant la même clé. Cette propriété est utile pour trier des objets selon plusieurs critères, par exemple des utilisateurs par âge tout en conservant leur ordre initial pour ceux qui ont le même âge.
La principale faiblesse reste la lenteur. Pour une application réelle, je n’utiliserais pas cette méthode sur plusieurs milliers d’éléments sans raison précise. Les fonctions intégrées sorted() et list.sort() sont généralement bien plus efficaces et ont été conçues pour les usages courants.
Adapter le tri à l’ordre décroissant et à d’autres données
Pour obtenir un ordre décroissant, il suffit d’inverser la comparaison. On échange alors les éléments lorsque le premier est plus petit que le second.
def tri_bulles_decroissant(liste):
n = len(liste)
for passage in range(n - 1):
echange = False
for i in range(n - 1 - passage):
if liste[i] < liste[i + 1]:
liste[i], liste[i + 1] = liste[i + 1], liste[i]
echange = True
if not echange:
break
nombres = [5, 2, 4, 1, 3]
tri_bulles_decroissant(nombres)
print(nombres)
# [5, 4, 3, 2, 1]On peut aussi trier des chaînes de caractères, à condition qu’elles soient comparables entre elles. En revanche, une liste contenant à la fois des nombres et des chaînes provoquera une erreur avec les comparaisons classiques, car Python ne peut pas déterminer un ordre naturel entre ces types.
Pour des dictionnaires ou des objets, il faut comparer une propriété précise. C’est faisable, mais le code devient vite moins lisible que l’utilisation de sorted() avec le paramètre key. Dans mes exercices, je réserve donc le tri à bulles aux valeurs simples et aux démonstrations d’algorithmique.
Quand choisir cette méthode plutôt que sorted
Le tri à bulles est un excellent outil pédagogique. Il oblige à comprendre les indices, les boucles imbriquées, les conditions et l’échange de variables. C’est aussi un bon exercice pour apprendre à mesurer le coût d’un algorithme au lieu de regarder uniquement s’il produit le bon résultat.
Dans un programme destiné à être utilisé par d’autres personnes, le choix est différent. Pour trier une liste, sorted(liste) renvoie une nouvelle liste, tandis que liste.sort() modifie la liste sur place. Ces solutions sont plus concises, plus robustes et généralement beaucoup plus rapides sur des volumes importants.
| Solution | Modifie la liste | Usage recommandé |
|---|---|---|
| Tri à bulles | Oui selon l’implémentation | Apprentissage et petites listes |
sorted(liste) |
Non | Créer une liste triée séparée |
liste.sort() |
Oui | Trier directement une liste existante |
Le tri manuel reste pertinent lorsqu’un cours, un entretien technique ou un projet impose de coder l’algorithme soi-même. Dans les autres cas, réinventer une fonction de tri apporte rarement un bénéfice. Le bon réflexe consiste à distinguer l’objectif pédagogique de l’objectif de performance.
Les détails qui rendent une implémentation fiable
Avant de lancer le tri, je vérifie toujours le comportement attendu pour une liste vide, une liste à un seul élément et une liste contenant des doublons. Ces cas ne nécessitent aucun échange et doivent retourner un résultat cohérent sans provoquer d’erreur.
- Une liste vide reste vide.
- Une liste d’un élément reste inchangée.
- Les doublons sont conservés.
- Les nombres négatifs sont triés comme les autres valeurs.
- Les types mélangés doivent être évités, sauf si une règle de comparaison explicite est définie.
Le piège le plus courant consiste à parcourir la liste jusqu’au dernier indice sans tenir compte de i + 1. Cela provoque une erreur d’indexation. Une autre erreur fréquente est d’oublier de réduire la limite intérieure, ce qui ne casse pas toujours le résultat, mais ajoute des comparaisons inutiles.
Pour tester la fonction, j’utilise plusieurs profils de listes plutôt qu’un seul exemple favorable.
tests = [
[],
[7],
[1, 2, 3, 4],
[4, 3, 2, 1],
[3, 1, 3, 2],
[-2, 5, 0, -1]
]
for valeurs in tests:
attendu = sorted(valeurs)
copie = valeurs.copy()
tri_bulles_optimise(copie)
assert copie == attendu
print("Tous les tests sont réussis")La comparaison avec sorted() ne sert pas à réécrire l’algorithme, mais à vérifier automatiquement le résultat. Pour moi, c’est la meilleure manière de transformer un exercice de programmation en code réellement fiable.
Ce que le tri à bulles apprend vraiment en Python
Le tri à bulles n’est pas le choix le plus rapide pour trier des données en production, et il ne faut pas le présenter comme tel. Sa valeur se trouve ailleurs : il rend visibles les notions de comparaison, d’invariant, de complexité et de modification sur place.
Une fois l’algorithme compris, il devient plus facile d’évaluer d’autres méthodes comme le tri par insertion, le tri par sélection ou les fonctions natives de Python. Retenez surtout cette règle pratique : utilisez le tri à bulles pour apprendre et expérimenter, puis préférez sorted() ou sort() dès que la performance et la simplicité du projet comptent réellement.
