Algorithmes Python

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.

  • Intermédiaire
  • 2 min de lecture
  • 1 exemple exécutable

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.

De la file d'enfants au code
result[index] > result[index + 1]👫 Le plus grand est-il devant ?
result[index], result[index + 1] = ...🔄 Échanger les deux voisins
for end in range(len(result) - 1, 0, -1):🚶 Reparcourir la file, un enfant de moins à chaque fois
if not swapped: break✅ Aucun échange sur tout un passage : la file est triée
Après chaque passage, la plus grande valeur restante est à sa place définitive.
En une phrase

Le 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

  1. result = values.copy() trie une copie, donc la liste de l'appelant n'est pas modifiée.
  2. if result[index] > result[index + 1]: échange une paire mal ordonnée.
  3. end diminue après chaque passage, car les plus grandes valeurs sont déjà à la fin.
  4. if not swapped: break arrê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() et list.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

Exécuter le code →
main.py
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]))
Obtenir un bouton Run pour cet exemple

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.

  1. Testez avec une liste vide, une liste d’un seul élément et une liste avec des doublons.
  2. Affichez l’état après chaque étape pour observer l’algorithme en action.
  3. Mesurez le temps d’exécution avec 100, 1 000 et 10 000 éléments, puis comparez avec une autre solution.
Exécuter dans le compilateur Python →

Erreurs fréquentes

Aller un indice trop loin

result[index + 1] dépasse la fin quand index atteint la dernière position.

Problème
for index in range(len(result)):
    if result[index] > result[index + 1]:
Correction
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.

Tous les défis