Le tri par insertionChapitre 4/8

Ranger les cartes dans sa main

Tu joues aux cartes. On te distribue tes cartes une par une, et tu les ranges au fur et à mesure. Quand une nouvelle carte arrive, tu ne recommences pas tout : ta main est déjà rangée. Tu fais glisser la nouvelle carte de droite à gauche, en passant les cartes plus grandes qu'elle, et tu la poses dès que tu tombes sur une carte plus petite.

C'est le tri par insertion. Le tableau a deux zones : à gauche, la main (déjà triée), à droite, les cartes encore sur la table. Au départ, la main ne contient que la première carte : une seule carte, c'est forcément trié. Puis on prend les cartes suivantes une par une.

À retenirPourquoi « insertion » ? Parce qu'à chaque passage, on insère une nouvelle carte à sa place parmi celles déjà triées. On ne va pas chercher la plus petite (ça, c'était la sélection) : on prend simplement la carte suivante, quelle qu'elle soit, et on lui trouve sa place.

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.