Algorithmes de tri

Mettre les choses en ordre — la façon maligne !

Niveau Débutant — langage simple, sans maths

Imagine une grosse pile de cartes numérotées, toutes mélangées, et la tâche de les mettre en ordre de la plus petite à la plus grande. Tu pourrais les parcourir à la main, comparant et casant chacune à sa place. Assez facile avec dix cartes. Avec un million, la même méthode patiente t'occuperait des années.

Les ordinateurs rencontrent exactement ce problème toute la journée — trier tes e-mails par date, tes photos par heure, les résultats de recherche par pertinence, les contacts de A à Z. Un algorithme de tri n'est que la recette précise, étape par étape, qu'un ordinateur suit pour le faire. Et voici ce sur quoi il vaut la peine de s'arrêter : pour la même pile de cartes, certaines recettes sont des millions de fois plus rapides que d'autres.

Le plus simple, le Bubble Sort, parcourt la liste en comparant les voisins, échangeant ceux qui sont en désordre, et répète jusqu'à ce qu'il ne reste rien à échanger. Il marche, mais il est lent — il vérifie essentiellement chaque paire. L'alternative maligne, le Merge Sort, joue au diviser-pour-régner : coupe la pile en deux, trie chaque moitié, puis recoud les deux moitiés triées. Divise et fusionne, divise et fusionne, et le million de cartes qui aurait pris des années tombe en ordre en un clin d'œil. Même tâche, stratégie follement différente — c'est tout le jeu.

Complexité Big-O : mesurer l'efficacité d'un algorithme

Niveau Élève — les équations essentielles

La qualité d'un algorithme de tri se ramène à une question : à mesure que l'entrée grandit jusqu'à \(n\) éléments, à quelle vitesse le travail grandit-il ? La notation Big-O capture exactement ce taux de croissance, dans le pire cas. Le truc est que la vitesse brute dépend de ton matériel, mais le taux de croissance est inscrit dans l'algorithme lui-même — et c'est le taux de croissance qui décide qui gagne sur un million d'éléments.

Le Bubble Sort ne cesse de balayer la liste, faisant remonter les grandes valeurs vers la droite un échange à la fois. Pour \(n\) éléments c'est jusqu'à \(\tfrac{n(n-1)}{2}\) comparaisons — \(O(n^2)\). Double l'entrée et tu quadruples le travail. À \(n = 10^6\) c'est environ 500 milliards de comparaisons, à peu près 8 minutes sur une machine faisant un milliard par seconde.

Le Merge Sort prend la voie du diviser-pour-régner : divise en deux, trie récursivement chaque moitié, puis fusionne. Chaque fusion est un travail \(O(n)\) et la récursion n'a que \(\log_2 n\) niveaux de profondeur, donc le total est \(O(n \log n)\). À \(n = 10^6\) c'est environ 20 millions de comparaisons — quelque 25 000 fois plus rapide que le Bubble Sort. Le prix est la mémoire : la fusion nécessite \(O(n)\) d'espace de travail.

Le QuickSort choisit un pivot, divise le tableau en « plus petits » et « plus grands », et récurse de chaque côté. En moyenne il est \(O(n \log n)\) avec un délicieux comportement de cache ; son pire cas est \(O(n^2)\) sur une entrée déjà triée, dompté en choisissant le pivot au hasard. Les vrais langages couvrent leurs paris : Python et Java embarquent le TimSort, un hybride Merge/Insertion qui repère les séquences déjà en ordre et fonce à travers des données presque triées en quasi \(O(n)\).

Complexité computationnelle, le théorème maître et les preuves de borne inférieure

Niveau Expert — profondeur mathématique complète

01Résoudre les récurrences : le théorème maître

Les algorithmes diviser-pour-régner se décrivent par des récurrences, et la plupart entrent dans un unique modèle : \(T(n) = a\,T(n/b) + f(n)\) — \(a\) sous-problèmes de taille \(n/b\), plus \(f(n)\) de travail pour diviser et recombiner. Le théorème maître lit la réponse en comparant \(f(n)\) à \(n^{\log_b a}\) : celui qui domine gagne, et s'ils font match nul tu payes un \(\log n\) supplémentaire. Le Merge Sort a \(a=b=2\) et \(f(n)=\Theta(n)\), ce qui est exactement le cas d'égalité \(n^{\log_2 2} = n\) — d'où \(T(n) = \Theta(n \log n)\), sans aucun tour de passe-passe.

02La borne inférieure que personne ne peut battre

Le Merge Sort est \(O(n\log n)\) — mais quelque chose de plus malin pourrait-il être plus rapide ? Pour tout tri qui fonctionne en comparant des éléments, la réponse est un non catégorique, et la preuve est superbe. Modélise l'algorithme comme un arbre de décision binaire : chaque nœud interne pose une comparaison, chaque feuille est une permutation finie. Trier \(n\) éléments signifie que l'arbre doit avoir au moins \(n!\) feuilles pour distinguer chaque ordre, et un arbre binaire de hauteur \(h\) en a au plus \(2^h\). Donc \(h \ge \log_2(n!)\), et Stirling transforme cela en \(\Omega(n \log n)\). La borne est théorique-informationnelle — elle se moque de ta malice, seulement du nombre d'issues à distinguer.

03Battre la borne en trichant (légalement)

Ce mur ne s'applique qu'aux tris qui comparent. Sors de là et tu peux aller plus vite en exploitant la structure des données. Le Counting Sort dénombre les entiers dans une plage connue \([0,k]\) en \(O(n+k)\) ; le Radix Sort enchaîne cela chiffre par chiffre pour \(O(d(n+k))\) ; le Bucket Sort atteint un \(O(n)\) espéré sur des données uniformément réparties. Aucun ne contredit la borne inférieure — ils font simplement de l'arithmétique sur les clés au lieu de demander « lequel est plus grand ? », et le théorème n'a jamais rien promis là-dessus.

04Le cas moyen du QuickSort

Le pire cas du QuickSort est un vilain \(O(n^2)\), et pourtant c'est le tri vers lequel la plupart des systèmes réels se tournent, car en moyenne il n'est pas seulement \(O(n\log n)\) mais \(O(n\log n)\) avec de minuscules constantes et une superbe localité de cache. La moyenne découle de la somme des probabilités que deux éléments soient jamais comparés, qui aboutit à \(E[T(n)] = 2n H_n - 2n\) avec \(H_n\) le nombre harmonique — carrément \(O(n\log n)\). Randomiser le pivot rend le mauvais cas astronomiquement improbable plutôt que simplement rare.

05La machine sous le modèle

Le Big-O compte les opérations, mais un vrai processeur tient énormément à la localité mémoire — un défaut de cache peut coûter des centaines de comparaisons « gratuites ». C'est pourquoi un algorithme \(O(n\log n)\) qui parcourt la mémoire dans l'ordre écrase souvent un algorithme théoriquement égal qui saute partout. Les algorithmes cache-oblivious (Frigo et al., 1999) exploitent la récursion pour atteindre un comportement de cache optimal à toutes les tailles de cache à la fois, sans jamais qu'on leur dise la taille — un rappel que le modèle asymptotique est une carte, pas le territoire.

06La place du tri dans le zoo de la complexité

Le tri siège confortablement dans P, la classe des problèmes résolubles en temps polynomial. Son fameux voisin est la question de savoir si \(P = NP\) — si tout problème dont la solution est rapide à vérifier est aussi rapide à résoudre. Le tri est facile ; le problème du voyageur de commerce, qui se contente de réordonner des villes, est NP-difficile et l'on croit qu'il exige un effort exponentiel. Un algorithme optimal rapide pour lui ferait s'effondrer \(P\) dans \(NP\) et emporterait la cryptographie moderne avec lui. Qu'une tâche aussi tranquille que mettre les choses en ordre côtoie un problème qui pourrait réécrire les mathématiques est le drame silencieux de la théorie de la complexité.