Cours gratuit, illimité, sans publicité et sans mot de passe (juste ton email), par Ilian, professeur particulier depuis 2020. Rien n'est jamais totalement gratuit : en échange, Head of Science peut t'écrire pour te présenter ses cours, et si celui-ci t'a servi, un avis Google à la fin aide beaucoup.
Le monde est plein de listes triées
Ouvre un dictionnaire au hasard : en deux secondes, tu sais si le mot que tu cherches est avant ou après. Ouvre maintenant un livre où les mots seraient rangés dans n'importe quel ordre : pour trouver « pomme », il faudrait tout lire, page par page.
C'est toute la raison d'être des tris. Un tableau trié n'est pas plus joli, il est plus utile : on y cherche plus vite, on y repère tout de suite le plus petit et le plus grand, les doublons se retrouvent côte à côte, le classement se lit directement.
- Le classement d'une course : les temps triés du plus petit au plus grand.
- Ton fil de messages : trié par date, le plus récent en haut.
- Les livres d'une bibliothèque : triés par auteur, pour qu'on les retrouve.
- Les résultats d'un site de vente : triés par prix, quand tu cliques sur « prix croissant ».
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.