Mesurer un tri : la complexitéChapitre 5/8
Pourquoi ne pas simplement chronométrer ?
Tu connais maintenant trois tris : à bulles, par sélection, par insertion. Lequel est le plus rapide ? Le réflexe, c'est de sortir un chronomètre. Mais le même programme met 2 secondes sur un vieil ordinateur et 0,2 seconde sur un neuf. Il tourne plus vite le matin si rien d'autre n'est ouvert. Le chronomètre mesure la machine autant que l'algorithme.
On fait donc comme pour comparer deux recettes de cuisine : au lieu de chronométrer deux cuisiniers différents, on compte les gestes de chaque recette. Pour un tri, les gestes, tu les connais depuis le chapitre 1 : les comparaisons et les échanges (ou décalages).
À retenirCe nombre de gestes ne dépend ni de l'ordinateur, ni du langage, ni de l'heure. Il ne dépend que de l'algorithme et du tableau qu'on lui donne. C'est ce qu'on appelle étudier la complexité d'un algorithme.
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.