Le tri à bulles (bubble sort) en Python
Dans cette leçon, vous allez implémenter le tri à bulles et ajouter un arrêt anticipé dès que la liste est triée.
Introduction
Le problème
Le tri est partout, et comprendre son fonctionnement aide à raisonner sur la vitesse. Le tri à bulles est l'algorithme de tri le plus facile à suivre pas à pas, d'où son rôle habituel de premier exemple, même si les vrais programmes en utilisent de plus rapides.
Imaginez-le ainsi
Le tri à bulles, c'est comme aligner des enfants par taille en n'échangeant jamais que deux voisins. Parcourez la file et échangez toute paire où le plus grand est devant. Après un passage, le plus grand enfant est arrivé au bout, comme une bulle qui remonte à la surface. Recommencez jusqu'à ce qu'un passage ne demande aucun échange.
result[index] > result[index + 1]👫 Le plus grand est-il devant ?result[index], result[index + 1] = ...🔄 Échanger les deux voisinsfor end in range(len(result) - 1, 0, -1):🚶 Reparcourir la file, un enfant de moins à chaque foisif not swapped: break✅ Aucun échange sur tout un passage : la file est triéeLe tri à bulles parcourt la liste encore et encore en échangeant les voisins mal ordonnés, jusqu'à ce qu'un passage complet ne fasse aucun échange ; il prend en général un temps O(n²).
Points clés
result = values.copy()trie une copie, donc la liste de l'appelant n'est pas modifiée.if result[index] > result[index + 1]:échange une paire mal ordonnée.enddiminue après chaque passage, car les plus grandes valeurs sont déjà à la fin.if not swapped: breakarrête tôt quand un passage ne fait aucun échange, donc une liste déjà triée se termine après un passage.
Quand l’utiliser ?
- Apprendre comment fonctionne un tri par comparaisons.
- Les toutes petites listes dans les outils pédagogiques et les visualisations.
- Vérifier en un passage si une liste est déjà triée.
Quand s'en passer
- Tout vrai programme :
sorted()etlist.sort()sont bien plus rapides (O(n log n)) et testés. - Les listes de plus de quelques centaines d'éléments : le nombre de comparaisons croît comme le carré de la longueur.
Visualisation de Le tri à bulles (bubble sort) en Python
O(n²)Utilisez Lecture ou Étape pour suivre chaque comparaison et déplacement de données.
Code d’exemple
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
Résultat de l’exécution
[1, 2, 4, 5, 8]
Explication du code
Après chaque passage, la plus grande valeur de la partie non triée est déjà à sa place définitive, le passage suivant est donc plus court d'un élément. La variable swapped indique s'il y a eu un échange pendant le passage. S'il n'y en a eu aucun, la liste est déjà triée et la boucle s'arrête plus tôt. Dans le pire des cas, la complexité est O(n²), cet algorithme ne convient donc pas aux gros volumes de données.
Modifiez les valeurs et exécutez le programme avec le compilateur Python en ligne CodeUtility, sans installation locale.
Exercices d’approfondissement
Essayez de modifier le code en suivant les pistes ci-dessous. Changer le code et observer le résultat vous fera bien mieux comprendre la leçon que la simple lecture.
- Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
- Affichez l’état après chaque étape pour observer l’algorithme en action.
- Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Erreurs fréquentes
Aller un indice trop loin
result[index + 1] dépasse la fin quand index atteint la dernière position.
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
Leçon terminée ?
Marquez-la comme apprise pour suivre votre progression.
S'entraîner avec un défi
Utilisez le contenu de cette leçon pour résoudre un vrai problème. Chaque défi s'exécute dans le navigateur, avec des tests instantanés et une revue par l'IA.
- Count Inversions Count the out-of-order pairs in a list. Difficile
- Médiane d'une liste Trouvez la valeur centrale d'une liste après l'avoir triée. Facile