Bilan : quel tri choisir, et ce que fait PythonChapitre 8/8
Les cinq tris en un tableau
Voici tout le cours résumé. Les complexités comptent les comparaisons, pour un tableau de n valeurs. La colonne « en place » dit si le tri travaille dans le tableau lui-même (chapitre 5), « stable » s'il garde l'ordre de départ des valeurs égales.
| Tri | Meilleur cas | Cas moyen | Pire cas | En place | Stable | NSI |
|---|---|---|---|---|---|---|
| à bulles (avec arrêt) | O(n), déjà trié | O(n²) | O(n²) | oui | oui | pas cité (souvent vu en classe) |
| par sélection | O(n²) | O(n²) | O(n²) | oui | non | Première |
| par insertion | O(n), déjà trié | O(n²) | O(n²), à l'envers | oui | oui | Première |
| fusion | O(n log n) | O(n log n) | O(n log n) | non | oui | Terminale |
| rapide | O(n log n) | O(n log n) | O(n²), pivot extrême | oui (version en place) | non | pas cité |
AstucePour lire ce tableau : O(n²) veut dire « doubler n multiplie le travail par 4 », O(n log n) « doubler n multiplie le travail par un peu plus de 2 », O(n) « doubler n double le travail ». Pour n = 1000 : environ 500 000, 10 000 et 1 000 comparaisons.
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.