Un élève pivot
Retour dans la cour, avec une classe à ranger par taille. Cette fois, le prof désigne un élève au hasard, Léa, et annonce : « Ceux qui sont plus petits que Léa, à sa gauche. Les autres, à sa droite. » En une seule annonce, chacun se compare à Léa et choisit son côté.
Que sait-on maintenant ? Le groupe de gauche n'est pas rangé, celui de droite non plus. Mais Léa, elle, est exactement à sa place : tous ceux qui sont avant elle sont plus petits, tous ceux qui sont après sont plus grands. Il reste à ranger le groupe de gauche, puis celui de droite, avec la même méthode : un nouveau pivot dans chaque groupe, et ainsi de suite.
Léa s'appelle le pivot, et répartir les autres autour d'elle s'appelle une partition. C'est le tri rapide, inventé par Tony Hoare en 1959 sous le nom de *quicksort*.
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.