Exercice 43 / 100

Tri - bubble sort

Implémentez le tri à bulles

Le tri à bulles est l'algorithme de tri le plus simple à comprendre. À chaque passage, on compare les éléments deux à deux et on échange ceux qui ne sont pas dans le bon ordre. Les grandes valeurs "remontent" vers la fin comme des bulles.

Idée

1. parcourir la liste de gauche à droite
2. si arr[j] > arr[j+1], les échanger
3. à la fin du parcours, le plus grand élément est à la fin
4. recommencer (un de moins à chaque fois)

Le tri à bulles compare les éléments deux à deux et les échange si besoin : à chaque passage la plus grande valeur remonte à la fin, puis on recommence

Échanger deux variables

En Python, on swap en une ligne (déballage de tuple) :

arr[j], arr[j+1] = arr[j+1], arr[j]

Pas besoin d'une variable temporaire comme dans d'autres langages.

Implémentation

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))
# → [11, 12, 22, 25, 34, 64, 90]

Complexité

Pire / moyen cas  →  O(n²)
Meilleur cas      →  O(n) avec une optimisation early-exit
Mémoire           →  O(1) — tri en place

O(n²) est lent : pour n = 10 000, c'est 100 millions d'opérations. Inutilisable en pratique pour de gros volumes.

En vrai, en Python

arr.sort()             # tri en place (Timsort, O(n log n))
sorted(arr)            # renvoie une nouvelle liste triée

Le tri à bulles s'enseigne pour comprendre les algorithmes, pas pour être utilisé. Toujours utiliser sort() / sorted() en production.

Algorithmes de tri à connaître (par ordre de mérite) : Timsort (Python), Quicksort, Mergesort, Heapsort.

exercise.py