Le tri par sélectionChapitre 3/8

Le prof qui choisit le plus petit

Reprenons la classe à ranger par taille. Cette fois, le prof change de méthode. Il regarde tous les élèves qui ne sont pas encore rangés, repère le plus petit, et lui dit : « toi, viens en tête du rang ». L'élève qui occupait cette place prend la sienne. Le premier du rang est maintenant le bon, et il ne bougera plus.

Puis le prof recommence avec les élèves restants : il repère le plus petit d'entre eux, et l'envoie en deuxième position. Et ainsi de suite, jusqu'au dernier.

C'est le tri par sélection. Le tableau est coupé en deux zones : à gauche, la partie triée, qui grandit d'une case à chaque passage ; à droite, la partie non triée, où l'on va chercher le minimum.

À retenirPourquoi « sélection » ? Parce qu'à chaque passage, on sélectionne le plus petit élément de la partie non triée. Comme quand tu ranges des cartes posées en vrac sur la table : tu choisis la plus petite, tu la mets dans ta main, puis tu choisis la plus petite de celles qui restent, et ainsi de suite.

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.