Le tri à bullesChapitre 2/8

Des élèves qui se rangent par taille

Une classe en rang, à ranger du plus petit au plus grand. Le prof n'a pas de mètre ruban, et il ne regarde que deux élèves à la fois. Il se place devant les deux premiers : si celui de gauche est plus grand, ils échangent leur place. Il fait un pas à droite et recommence avec les deux suivants, jusqu'au bout du rang.

Après ce premier tour, une chose est sûre : le plus grand de la classe est au bout du rang. Où qu'il ait été au départ, dès que le prof l'a rencontré, il a gagné tous ses duels et avancé d'une place à chaque pas, jusqu'à la fin.

C'est le tri à bulles. Chaque tour du prof s'appelle un passage. On recommence les passages jusqu'à ce que tout le rang soit en ordre.

À retenirPourquoi « bulles » ? Dans un verre de soda, les bulles d'air remontent à la surface. Ici, les grandes valeurs « remontent » vers la fin du tableau, une case à chaque échange, comme une bulle qui monte. Dessine le tableau à la verticale, la case 0 en bas : tu verras les grosses bulles filer vers le haut.

Programme complet du cours sur les tris (8 chapitres, gratuit)

1. Pourquoi trier, et avec quels gestes : À quoi sert un tableau trié, ce qu'on appelle exactement « trier », et les deux seuls gestes qu'un algorithme de tri a le droit de faire : comparer et échanger.
2. Le tri à bulles : Comparer les voisins deux par deux et échanger ceux qui sont mal rangés : les grandes valeurs remontent au bout du tableau comme des bulles dans un verre de soda.
3. Le tri par sélection : Chercher le plus petit de ce qui reste, le mettre devant, recommencer : on sélectionne le minimum à chaque passage, avec un seul échange.
4. Le tri par insertion : Comme quand tu ranges les cartes dans ta main : chaque nouvelle carte est insérée à sa place parmi celles déjà triées, en faisant glisser les plus grandes.
5. Mesurer un tri : la complexité : Compter les comparaisons plutôt que chronométrer, comprendre ce que veut dire O(n²), distinguer meilleur et pire cas, prouver qu'un tri marche avec un invariant, et savoir ce qu'est un tri en place ou stable.
6. Le tri fusion : Diviser pour régner : couper le tableau en deux, trier chaque moitié, puis fusionner deux paquets triés. Avec, en chemin, les tranches de liste et la récursivité.
7. Le tri rapide : Choisir un pivot, ranger les plus petits d'un côté et les plus grands de l'autre, puis recommencer de chaque côté. Rapide en moyenne, mais pas toujours : on verra pourquoi.
8. Bilan : quel tri choisir, et ce que fait Python : Les cinq tris côte à côte (complexités, en place, stable, programme NSI), puis sorted() et list.sort() : ce que Python utilise vraiment (Timsort), et pourquoi on apprend quand même les autres.