00 — Pourquoi étudier le tri quand sort() existe déjà
Ce que tu vas apprendre
- Pourquoi le tri reste un sujet d'étude alors que
sort()est partout - Les questions qu'on se pose face à un tri : stabilité, mémoire, cas pire
- Le vocabulaire commun à toute la série
- Le plan des 8 articles
Prérequis
- La notation Big-O de la série Complexité
- Savoir lire une fonction en TypeScript ou Python
La première réaction est légitime : pourquoi apprendre à trier alors que [3, 1, 2].sort() fait le travail en une ligne ? Personne de sensé ne réécrit un tri en production. Et pourtant, le tri est l'exemple le plus pédagogique de toute l'algorithmie. C'est un problème simple à énoncer, avec une dizaine de solutions aux complexités très différentes, allant de O(n²) à O(n log n). Comprendre pourquoi un tri est lent et un autre rapide, c'est comprendre la complexité en action.
Il y a aussi des raisons pratiques. Un jour, tu liras une trace de performance et tu verras que sort() mange 60 % du temps de réponse. Tu voudras savoir pourquoi. Un autre jour, un tri changera l'ordre de deux éléments qui te semblaient identiques, et tu découvriras la notion de stabilité à tes dépens. Connaître les algorithmes derrière sort() te permet de déboguer ces situations au lieu de les subir.
Les questions qu'on pose à un algorithme de tri
Tous les tris produisent le même résultat : une liste ordonnée. Ce qui les distingue, ce sont leurs propriétés. Trois questions reviennent tout au long de cette série.
Quelle est sa complexité en temps ? C'est la première chose à regarder. Certains tris sont en O(n²), inutilisables au-delà de quelques milliers d'éléments. D'autres sont en O(n log n), la limite théorique des tris par comparaison. Et on verra qu'on peut même descendre à O(n) dans des cas particuliers, en abandonnant la comparaison.
Est-il stable ? Un tri est stable s'il préserve l'ordre relatif des éléments égaux. Si tu tries une liste d'employés déjà triée par prénom, en triant cette fois par service, un tri stable gardera les employés d'un même service dans l'ordre alphabétique des prénoms. Un tri instable peut les mélanger. Ça compte dès qu'on trie sur plusieurs critères successifs.
Trie-t-il en place ? Un tri en place réorganise le tableau sans allouer de structure auxiliaire significative, donc en O(1) d'espace supplémentaire. D'autres ont besoin d'une copie de travail, donc O(n) d'espace. C'est le compromis temps/espace de la série Complexité, appliqué au tri.
Le vocabulaire de la série
Pour suivre les articles sans accroc, quelques termes :
- Comparaison : l'opération de base d'un tri classique, du type
a < b. Les tris par comparaison sont limités à O(n log n) au mieux, c'est un résultat démontré. - Échange (swap) : intervertir deux éléments. On compte parfois les échanges séparément des comparaisons, car ils peuvent coûter cher sur de gros objets.
- Pivot : un élément de référence autour duquel on partitionne, central dans le tri rapide.
- Diviser pour régner : découper le problème en sous-problèmes plus petits, les résoudre, puis recombiner. C'est le principe des tris fusion et rapide.
Le plan de la série
On part des tris simples mais lents, pour finir sur ce que font vraiment les langages modernes.
| Article | Contenu |
|---|---|
| 00 — Introduction | Pourquoi étudier le tri (cet article) |
| 01 — Sélection et insertion | Les deux tris quadratiques à connaître |
| 02 — Tri à bulles | Le tri qu'on enseigne et qu'on n'utilise pas |
| 03 — Tri par fusion | Diviser pour régner, O(n log n) garanti |
| 04 — Tri rapide | Le plus utilisé, et son pire cas O(n²) |
| 05 — Tri par tas | Trier avec une file de priorité |
| 06 — Tris linéaires | Comptage et radix, battre O(n log n) |
| 07 — En pratique | Stabilité, en place, et le Timsort réel de sort() |
À la fin, tu sauras quel tri se cache derrière sort() (un indice : ce n'est aucun des tris « purs »), pourquoi le tri rapide reste populaire malgré son pire cas catastrophique, et dans quels cas rares on peut trier plus vite que O(n log n).
L'article suivant commence par les deux tris les plus intuitifs, ceux qu'on réinvente naturellement quand on n'a jamais étudié la question : sélection et insertion.
Sources
- Videau, M., & Eck, D. (2004). Les algorithmes de tri. Interstices. interstices.info/les-algorithmes-de-tri/
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapitre 2 "Getting Started". MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Chapitre 2 "Sorting". Addison-Wesley.
- Knuth, D. E. (1998). The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.). Addison-Wesley.