Tri à Bulle (Bubble Sort)
Échanges successifs — la bulle qui remonte
Enonce
Implémenter le tri à bulle en place avec la variante optimisée : si aucun échange n'a lieu pendant un passage, le tableau est trié et on s'arrête.
⚠ Contrainte : Tri en place, retourne None.
Signature attendue
def tri_bulle(T: list) -> None:Exemple
T = [64, 34, 25, 12, 22, 11, 90] ; tri_bulle(T) ; T→[11, 12, 22, 25, 34, 64, 90]
📖 Rappel de cours
Le tri à bulle compare les éléments deux à deux et les échange s'ils sont dans le mauvais ordre. On répète les passages jusqu'à ce qu'il n'y ait plus d'échanges.
🫧 Analogie — Les bulles qui remontent :
Imaginez des bulles dans un verre d'eau. Les plus légères (les plus grands éléments) remontent naturellement vers la surface. À chaque passage, le plus grand élément non trié « remonte » à sa place finale, comme une bulle qui flotte vers le haut. Après $n-1$ passages, toutes les bulles sont à leur place !
Invariant :
Après le passage $i$, les $i$ plus grands éléments sont à leur position définitive en fin de tableau.
Complexité :
$C(n) = \frac{n(n-1)}{2} = O(n^2)$
Meilleur cas (déjà trié) : $O(n)$ avec la variante optimisée (détection d'absence d'échanges).
← Exercices d'algorithmique en Python — tris, dichotomie, récursivité
Exercices du meme theme
- Recherche Dichotomique
- Suite de Fibonacci
- Tri par Insertion
- Tri par Sélection
- Tri Fusion (Merge Sort)
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.