Les tris simples : comment ils pensent#
Un algorithme, c'est une suite d'étapes précises qui résout un problème à coup sûr. Le problème le plus universel de l'informatique : trier (un répertoire, des prix, des résultats de recherche...). Il en existe des dizaines de méthodes. Commençons par les trois plus intuitives - celles qu'on inventerait nous-mêmes.
Tri à bulles
On compare deux voisins ; si le plus grand est à gauche, on les échange. À force de passages, les grandes valeurs « remontent » comme des bulles vers la fin.
Tri par sélection
On cherche le plus petit de tout le reste, on le met en premier. Puis le plus petit du reste, en deuxième. Et ainsi de suite.
Tri par insertion
Comme on range des cartes en main : on prend la suivante et on la glisse à sa bonne place parmi celles déjà triées.
Ils sont faciles à comprendre et à écrire. Leur défaut se cache dans le nombre de comparaisons - on va le voir juste en dessous, puis le chiffrer.
Regarde-les travailler#
Mêmes barres, même désordre de départ. Choisis un algorithme, clique Trier, et observe : orange = deux barres comparées, rose = une barre déplacée, aqua = en place. Le compteur de comparaisons est le juge de paix.
Combien ça coûte vraiment ? La notation O()#
« Simple » et « avancé » ne sont pas des impressions : on les mesure. On compte combien d'opérations un algorithme demande quand la donnée grandit, et on résume cette croissance avec la notation Grand O. C'est le concept central de l'algorithmique.
O(n)- le travail grandit au même rythme que la donnée (parcourir une liste).O(n log n)- à peine plus que proportionnel. Le palier des bons tris.O(n²)- double la donnée, quadruple le travail. Le palier des tris simples.
Pour saisir l'écart, mets un nombre d'éléments et regarde le travail exploser - ou pas.
Fais grandir la donnée, mesure l'explosion
En supposant un milliard d'opérations par seconde. L'idée à emporter : à 1 million d'éléments, un tri en O(n²) demande mille milliards d'opérations (des minutes), là où un O(n log n) en demande vingt millions (un clin d'œil). C'est ça, la différence entre simple et avancé.
Les tris avancés & le secret de Python#
Les tris rapides reposent tous sur la même ruse : diviser pour régner. Plutôt que de comparer chaque paire, on casse le problème en deux moitiés, on règle chacune, et on recombine. Cette idée fait tomber le coût de O(n²) à O(n log n).
On coupe la liste en deux jusqu'à des morceaux d'un seul élément (déjà triés !), puis on les fusionne deux à deux en gardant l'ordre. Régulier, prévisible, toujours en O(n log n).
On choisit un pivot, on met les plus petits à gauche et les plus grands à droite, puis on recommence sur chaque côté. Très rapide en pratique, c'est souvent le plus efficace.
Quand tu écris sorted(mesures) ou mesures.sort(), Python n'utilise aucun des tris d'école : il lance Timsort, un hybride malin de tri par insertion et de tri fusion, inventé par Tim Peters en 2002 pour Python. Il repère les bouts déjà ordonnés dans tes données réelles et va encore plus vite.
| Tri | Famille | Idée maîtresse |
|---|---|---|
| Bulles / Sélection / Insertion | O(n²) | Comparer beaucoup, simple à écrire |
| Fusion | O(n log n) | Couper en deux, puis fusionner |
| Rapide | O(n log n) | Partager autour d'un pivot |
Timsort (sorted) | O(n log n) | Hybride qui exploite l'ordre déjà présent |
Pourquoi on se donne la peine de trier#
Trier coûte un effort. La récompense : on peut ensuite chercher à la vitesse de l'éclair. Dans une liste en désordre, trouver une valeur oblige à tout regarder (O(n)). Dans une liste triée, on utilise la recherche dichotomique : on vise le milieu, on élimine la moitié qui ne peut pas contenir la cible, et on recommence. Chaque essai divise par deux ce qui reste : O(log n).
Pense à un nombre entre 1 et 1000. L'ordinateur va le deviner en 10 essais maximum - réponds-lui simplement.
Le jeu du plus / moins : la dichotomie en action
Pour aller plus loin#
Les algorithmes ne servent pas qu'à trier : ils tracent ton chemin dans le GPS (Dijkstra), classent les pages web (PageRank), compressent tes photos (JPEG) et chiffrent tes mots de passe. Trier et chercher vite, c'est la porte d'entrée de tout ce monde.
Et d'où vient cette idée même d'« algorithme » ? Le mot a mille ans, le plus vieux tient depuis l'Antiquité, et le tout premier programme pour machine a été écrit par une femme au 19e siècle. 🧑🚀 Découvre l'histoire des algorithmes →