Le tri fusionChapitre 6/8

32 copies à classer

Ton prof doit classer 32 copies par ordre alphabétique. Seul, avec un tri par insertion, il en a pour un moment. Alors il coupe la pile en deux et en donne une moitié à un collègue. Chacun trie ses 16 copies. Il reste à assembler deux piles déjà triées en une seule.

Et ça, c'est facile : il pose les deux piles côte à côte, face visible. Il ne regarde que les deux copies du dessus, prend celle qui vient en premier dans l'alphabet et la pose sur la pile finale. Une nouvelle copie apparaît sur le dessus, il recommence. Une seule comparaison par copie, jamais de retour en arrière.

À retenirPourquoi « fusion » ? Parce que le coeur de l'algorithme est cette étape : on fusionne deux paquets triés en un seul paquet trié, comme deux files de voitures qui se rejoignent en une seule voie, une voiture de chaque côté à la fois.

Et le collègue, comment trie-t-il ses 16 copies ? Exactement pareil : il coupe en deux paquets de 8, en confie un, fusionne. Et ainsi de suite jusqu'à des paquets d'une seule copie, qui sont triés sans rien faire. Cette stratégie a un nom : diviser pour régner.

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.