📦 Le problème le plus banal de l'informatique
Tu as une liste de nombres en désordre. Tu veux les ranger du plus petit au plus grand. Facile, non ? À la main, avec dix cartes, oui. Mais un ordinateur, lui, doit suivre une recette précise — un algorithme — et la recette qu'il choisit change absolument tout quand la liste ne contient pas dix nombres, mais un million.
Le tri est sans doute l'opération la plus exécutée au monde : classer des résultats de recherche, ordonner des e-mails par date, afficher un classement, préparer des données avant de chercher dedans… Comprendre comment trier, c'est comprendre le cœur battant de l'algorithmique.
🎬 Les algorithmes de tri en action
Lance un tri et regarde les barres se ranger pas à pas. Jaune = en comparaison, vert = déjà trié.
Comparaisons
0
Échanges
0
Choisis un algorithme pour lancer le tri.
🫧 Les trois tris « simples »
Avant les algorithmes malins, il y a les algorithmes intuitifs : ceux qu'on inventerait spontanément. Ils sont faciles à comprendre, faciles à coder… et lents. Voici les trois grands classiques.
Tri à bulles (bubble sort). On parcourt la liste et, à chaque fois que deux voisins sont dans le mauvais ordre, on les échange. Les grandes valeurs « remontent » comme des bulles vers la fin. On recommence jusqu'à ce qu'aucun échange ne soit nécessaire. Simple, mais il échange énormément.
Tri par sélection (selection sort). On cherche le plus petit élément de toute la liste et on le place en première position. Puis le plus petit du reste, en deuxième position. Et ainsi de suite. Il fait beaucoup de comparaisons mais très peu d'échanges (un seul par tour).
Tri par insertion (insertion sort). C'est exactement la façon dont on range des cartes dans sa main : on prend chaque nouvelle carte et on la glisse à sa bonne place parmi celles déjà triées. Très efficace sur les listes presque triées — c'est d'ailleurs souvent le tri utilisé en pratique sur les petits tableaux.
⏱️ La grande idée : la complexité
Ce qui distingue ces algorithmes, ce n'est pas s'ils trient — ils trient tous correctement — mais combien d'opérations il leur faut. On mesure ça avec la complexité, notée avec un grand O : elle décrit comment le nombre d'opérations grandit quand la taille de la liste, n, augmente.
Nos trois tris simples sont tous en O(n²) : pour doubler la taille de la liste, ils prennent environ quatre fois plus de temps. Pourquoi ? Parce que chacun compare, grosso modo, chaque élément à tous les autres : n éléments × n éléments = n². Pour n = 40 barres dans la visualisation, c'est environ 1 600 opérations. Pas grave. Pour un million d'éléments…
n = 1 000 000. Un algorithme en O(n²) demande environ 1 000 000 000 000 (mille milliards) d'opérations. Même à un milliard d'opérations par seconde, ça prend plus de 15 minutes. Pour 100 millions d'éléments : des mois de calcul.
🚀 Les tris « malins » : O(n log n)
Heureusement, on sait faire infiniment mieux. Les meilleurs algorithmes de tri généralistes sont en O(n log n) — une croissance presque linéaire. Deux stars :
Le tri fusion (merge sort). Stratégie « diviser pour régner » : on coupe la liste en deux, on trie chaque moitié (récursivement), puis on fusionne les deux moitiés triées en une seule. Toujours O(n log n), même dans le pire des cas. Inventé par John von Neumann en 1945.
Le tri rapide (quicksort). Inventé par Tony Hoare en 1959, c'est le tri le plus utilisé au monde. On choisit un élément pivot, on place tout ce qui est plus petit à gauche et tout ce qui est plus grand à droite, puis on recommence sur chaque côté. En moyenne O(n log n), avec une vitesse réelle redoutable.
Que vaut « log n » ? Pour n = 1 000 000, log₂(n) vaut à peine 20. Donc n log n ≈ 20 millions d'opérations… contre mille milliards pour le O(n²). C'est 50 000 fois moins.
🌍 Pourquoi ça compte à grande échelle
Quand Google classe des milliards de pages, quand une banque trie des millions de transactions, quand ton téléphone ordonne des photos : le choix de l'algorithme n'est pas un détail théorique. C'est la différence entre une application instantanée et une application inutilisable.
🧠 Ce qu'il faut retenir
Trier paraît trivial parce qu'on le fait à petite échelle. Mais derrière ce geste banal se cache l'une des leçons les plus profondes de l'informatique : deux programmes qui donnent exactement le même résultat peuvent être séparés par un facteur d'un milliard.
Bulles, sélection, insertion pour comprendre ; fusion et tri rapide pour la vie réelle. Et au-dessus de tout : la notion de complexité, la boussole qui dit, avant même d'écrire une ligne de code, si un algorithme tiendra la charge ou s'effondrera.