Overview
Bubble Sort compare des elements adjacents et les echange quand ils sont dans le mauvais ordre. A chaque passe, le plus grand element restant va a droite.
Analogy
Comme des bulles dans l eau: les plus grosses montent vers le haut a chaque tour.
Step-by-step
- Parcourir la liste et comparer arr[j] avec arr[j+1].
- Si arr[j] > arr[j+1], faire un swap.
- Apres une passe, le plus grand element est place en fin de tableau.
- Reduire la zone de parcours car la fin est deja triee.
- Arreter plus tot si aucune permutation n est faite.
Visual
Passe 1: [5,3,8,1,2] -> [3,5,1,2,8], puis la fenetre se reduit a chaque passe.
Common mistakes
- Ne pas reduire la borne de la boucle interne.
- Utiliser >= au lieu de > et perdre la stabilite.
- Oublier l arret anticipe quand il n y a aucun swap.
Practice questions
- Tracer Bubble Sort sur une liste deja triee avec et sans arret anticipe.
- Montrer pourquoi Bubble Sort est stable.
- Modifier la logique pour trier en ordre descendant.
Time
O(n²) pire/moyenne, O(n) meilleur cas avec early exit