Tri et sélection

Objectifs du chapitre

À la fin de ce chapitre, vous serez capable de:

• écrire le tri par insertion, le tri fusion et le tri rapide en Python, et énoncer pour chacun le nombre de comparaisons dans le pire des cas, dans le cas favorable et en moyenne, en disant chaque fois sous quelle loi;
• démontrer la correction d'un tri par un invariant de boucle, et celle de la fusion de deux suites triées;
• dérouler la partition de Lomuto pas à pas, dire pourquoi un tableau déjà trié est son pire cas et ce que le pivot aléatoire achète exactement;
• démontrer la borne inférieure $\Omega (n\log n)$ des tris par comparaison par l'argument de l'arbre de décision, et dire précisément ce qu'elle interdit et ce qu'elle n'interdit pas;
• reconnaître les situations où le tri par comptage ou le tri par base s'appliquent, et nommer l'hypothèse qui leur vaut leur exemption;
• sélectionner le $k$-ième plus petit élément sans trier, et distinguer la garantie en moyenne de quickselect de la garantie au pire de la médiane des médianes;
• dire ce qu'est un tri stable, reconnaître les situations où cette propriété décide, et savoir lesquels des tris du chapitre la possèdent.

Le problème du tri, et ce que ce chapitre compte

L'énoncé, pour de bon

Trier paraît une tâche trop simple pour mériter un chapitre. C'est pourtant le problème le mieux étudié de toute l'algorithmique, et la raison en est double: il apparaît partout, comme sous-programme d'autre chose — chercher rapidement, détecter des doublons, calculer une médiane, construire un arbre couvrant minimal au chapitre 8 —, et il est l'un des très rares problèmes dont on connaisse à la fois un algorithme optimal et la preuve qu'on ne peut pas faire mieux. Ce chapitre contient les deux.

La seconde exigence est celle qu'on oublie, et c'est celle que vos tests doivent vérifier. La première se contrôle en un parcours; la seconde demande de comparer deux multi-ensembles. Nous y reviendrons dans les exercices.

Une relation d'ordre total signifie que deux éléments quelconques sont toujours comparables: pour tous $x$ et $y$, on a $x\le y$ ou $y\le x$. Cela vaut pour les nombres, pour les chaînes de caractères dans l'ordre lexicographique, pour les dates. Cela ne vaut pas pour un ordre partiel — l'inclusion entre ensembles, la divisibilité —, et trier n'a alors pas de sens; on parle plutôt de tri topologique, que le chapitre 6 traitera sur un graphe.

Trois adjectifs qui décrivent un tri

Ces trois propriétés sont indépendantes les unes des autres et de la classe de complexité, et elles décident souvent du choix d'un tri en pratique bien plus que le $\Theta$. La dernière section du chapitre revient longuement sur la stabilité, qui est de loin la plus sous-estimée des trois.

L'opération barométrique, et la convention de comptage

Comme au chapitre 1, nous ne chronométrons rien: nous comptons. L'opération barométrique d'un tri est la comparaison entre deux éléments du tableau, parce que c'est elle qui fait le travail et parce que, sur des objets réels — deux chaînes, deux dates, deux enregistrements —, elle est de loin l'opération la plus chère. Nous comptons aussi, quand c'est instructif, les décalages et les échanges, qui mesurent le trafic mémoire.

Un compte n'a de sens que si l'on dit ce qu'on a compté, et la même variante du tri par insertion donne 14, 15 ou 21 selon la convention retenue. Celle de tout ce cours, déjà utilisée au chapitre 1 et au chapitre 10 d'Introduction à la programmation, est la suivante, et elle ne varie pas d'un chapitre à l'autre:

• tri par insertion: une comparaison par test entre deux éléments du tableau, y compris le test qui fait sortir de la boucle intérieure, et rien lorsque l'indice tombe hors du tableau par la gauche;
• fusion: une comparaison par comparaison de deux éléments à l'intérieur de la boucle de fusion; les queues recopiées une fois qu'un côté est épuisé ne coûtent aucune comparaison;
• partition de Lomuto: une comparaison par tour de la boucle de partition.

Sur le tableau témoin du cours, a = [38, 27, 43, 3, 9, 82, 10], ces trois conventions donnent respectivement 15 comparaisons et 11 décalages, 13 comparaisons et 11 comparaisons. Ces trois nombres sont fixés pour tout le cours, et ce chapitre les retrouve tous les trois, par exécution et non par recopie. Les sept valeurs sont fictives; leur seule vertu est d'être toujours les mêmes, pour que vous puissiez comparer les traces d'un chapitre à l'autre.

Lisez la figure 3.1 colonne par colonne avant de lire une ligne de code: elle contient déjà la différence entre les trois méthodes. Le tri par insertion fait croître un préfixe trié d'une case par passe, et rien n'est acquis avant la fin. Le tri fusion assemble des morceaux triés de plus en plus longs, sans jamais revenir en arrière. Le tri rapide, lui, ne construit rien de croissant: il place un élément à sa place définitive et se contente de rendre vrai, autour de lui, un énoncé beaucoup plus faible — tout ce qui est à gauche lui est inférieur ou égal.

Le tri par insertion et son invariant

L'algorithme, et pourquoi on y revient

C'est le tri du joueur de cartes qui range sa main: on prend les éléments un par un, de gauche à droite, et on insère chacun à sa place dans la partie déjà triée, en décalant vers la droite tous ceux qui lui sont supérieurs.

def tri_insertion(a):
    """Trie une copie de a en inserant chaque element a sa place."""
    t = list(a)
    for i in range(1, len(t)):
        valeur = t[i]
        j = i - 1
        while j >= 0 and t[j] > valeur:
            t[j + 1] = t[j]          # decalage vers la droite
            j -=

Le chapitre 1 a compté ses comparaisons; ce chapitre s'intéresse à une question qu'il n'avait pas posée: pourquoi cet algorithme est-il correct? Que la boucle s'arrête est visible — j décroît strictement. Qu'elle produise un tableau trié qui soit une permutation de l'entrée demande un argument, et l'argument standard est celui de l'invariant de boucle. C'est un outil qu'on réutilisera au chapitre 7 pour Dijkstra et au chapitre 8 pour Kruskal; autant l'apprendre sur un algorithme qu'on connaît déjà.

L'invariant

L'invariant du tri par insertion est celui-ci, et il faut le lire attentivement, car la formulation naïve — «t[0:i] est trié» — est insuffisante.

Démonstration. Notons $a$ le tableau d'entrée et $t$ le tableau en cours de transformation. L'invariant $I(i)$ est la conjonction de deux propriétés: (i) t[0:i] est croissant, et (ii) le multi-ensemble des éléments de t[0:i] est exactement celui de a[0:i], tandis que t[i:n] coïncide encore avec a[i:n]. La seconde clause est indispensable: sans elle, l'invariant serait satisfait par un programme qui écrase le tableau avec des zéros.

Initialisation. Pour $i=1$, le sous-tableau t[0:1] a un seul élément, donc il est croissant, et il vaut a[0:1] puisque rien n'a encore été écrit. Le reste du tableau est intact. $I(1)$ est vraie.

Conservation. Supposons $I(i)$ vraie au début du tour d'indice $i$, avec $1\le i\le n-1$. Le corps de boucle range d'abord valeur = t[i], qui vaut a[i] par la clause (ii). Puis la boucle intérieure recule un indice $j$ depuis $i-1$ et, tant que $j\ge 0$ et , recopie en position .

Établissons un second invariant, celui de la boucle intérieure: à chaque test de sa condition, les cases t[j+2:i+1] contiennent, en ordre croissant, exactement les éléments de t[j+1:i] de l'état initial du tour, et tous sont strictement supérieurs à valeur; la case t[j+1] est libre, au sens où sa valeur est un doublon dont l'original a été copié une case à droite. C'est vrai au premier test, avec $j=i-1$: la tranche t[i+1:i+1] est vide et t[i] est bien libre, sa valeur étant sauvegardée dans valeur. C'est conservé par le corps: la recopie t[j+1] = t[j] ajoute t[j], strictement supérieur à valeur puisque la condition l'a testé, en tête d'une tranche dont tous les éléments lui sont supérieurs ou égaux — car t[0:i] était croissant — et libère t[j].

La boucle intérieure s'arrête dans exactement deux cas. Si elle s'arrête parce que $j<0$, alors tous les éléments de t[0:i] étaient strictement supérieurs à valeur, ils occupent désormais t[1:i+1] en ordre croissant, et l'affectation t[0] = valeur place valeur devant eux: t[0:i+1] est croissant. Si elle s'arrête parce que t[j] <= valeur, alors t[0:j+1] est croissant et son dernier élément est inférieur ou égal à valeur, la tranche t[j+2:i+1] est croissante et tous ses éléments sont strictement supérieurs à valeur, et l'affectation t[j+1] = valeur intercale valeur entre les deux: t[0:i+1] est croissant. Dans les deux cas la clause (i) de $I(i+1)$ est acquise.

La clause (ii) l'est aussi: le corps du tour n'a fait que des recopies d'une case vers sa voisine de droite, plus une écriture finale de la valeur sauvegardée; aucun élément n'a été perdu ni dupliqué, et rien n'a été écrit au-delà de l'indice $i$. Donc $I(i+1)$.

Terminaison. La boucle extérieure se termine avec $i=n$, la variable $i$ croissant strictement d'une unité par tour depuis 1. L'invariant $I(n)$ affirme alors que t[0:n], c'est-à-dire t tout entier, est croissant et contient exactement les éléments de a[0:n]. Les deux exigences de la définition du problème du tri sont satisfaites. $\square$

Trois remarques sur cette démonstration, parce qu'elle est le modèle de toutes celles du cours. D'abord, l'invariant porte les deux exigences du problème, pas seulement la plus visible; c'est le genre d'oubli qui laisse passer un tri faux. Ensuite, elle a fallu deux invariants emboîtés, un par boucle: c'est la règle, pas l'exception. Enfin, le travail réel s'est fait dans la conservation, et le cas $j<0$ y a demandé un traitement séparé — c'est exactement l'endroit où une implémentation se trompe d'une unité.

Le coût: trois régimes, et une moyenne

Le chapitre 1 a établi les comptes; rappelons-les, puisque ce chapitre les compare à ceux des autres tris. Notons $C(n)$ le nombre de comparaisons.

Dans le cas favorable, un tableau déjà croissant, chaque passe fait une seule comparaison — celle qui la fait sortir immédiatement — et aucun décalage: $C_{\min }(n)=n-1$. Dans le pire des cas, un tableau strictement décroissant, la passe $i$ traverse tout le préfixe: $C_{\max }(n)=1+2+\cdots +(n-1)=n(n-1)/2$. , sous la loi uniforme sur les permutations de éléments deux à deux distincts,

où $H_n=1+\frac{1}{2}+\cdots +\frac{1}{n}$ est le -ième nombre harmonique. Cette formule, démontrée au chapitre 1 et vérifiée par énumération exhaustive en fractions exactes pour , vaut pour . Le tableau témoin en coûte : à un dixième près, exactement le cas moyen.

Retenez la leçon de (3.1): son terme dominant est $n^2/4$, soit la moitié du pire des cas. En moyenne, chaque élément ne remonte que la moitié du préfixe trié. Le tri par insertion est donc quadratique en moyenne comme au pire, et ce n'est pas un algorithme que la moyenne sauve — contrairement au tri rapide, dont ce chapitre montrera qu'il est quadratique au pire et quasi-linéaire en moyenne.

Une qualité, toutefois, et elle est réelle: le tri par insertion est adaptatif. Son nombre de décalages est exactement le nombre d'inversions de la permutation d'entrée, c'est-à-dire le nombre de paires $(k,\ell )$ avec $k<\ell$ et $a[k]>a[\ell ]$. Sur des données presque triées — un journal presque ordonné par horodatage, un classement qui ne diffère du précédent que par quelques positions —, ce nombre est petit et le coût s'effondre vers le linéaire. C'est précisément pour cela que toutes les bibliothèques de tri sérieuses, y compris le Timsort de Python, basculent sur un tri par insertion sur les fragments courts et sur les portions déjà croissantes.

Le tri fusion, l'étalon en n log n

Rappel du chapitre 2

Le chapitre 2 a construit le tri fusion comme l'exemple canonique du schéma «diviser pour régner»: couper le tableau en deux moitiés, trier chacune récursivement, fusionner les deux résultats. Son coût obéit à la récurrence

dont le théorème maître, cas 2 avec $a=b=2$ et $f(n)=\Theta (n)=\Theta (n^{{\log }_{2}2})$, donne $T(n)\in \Theta (n\log n)$. Nous ne redémontrons pas ce point ici: il appartient au chapitre 2. Ce chapitre reprend le tri fusion pour trois raisons différentes — il sert d', la correction de sa fusion est l'obligation de démonstration de ce chapitre, et c'est lui qui atteindra la borne inférieure que nous démontrerons plus loin.

def tri_fusion(a: list[int]) -> list[int]:
    """Trie a par fusion: on coupe, on trie chaque moitie, on fusionne."""
    if len(a) <= 1:
        return list(a)
    milieu = len(a) // 2
    return fusion(tri_fusion(a[:milieu]), tri_fusion(a[milieu:]))

La fusion, et sa correction

Tout le travail est dans la fusion, et elle tient en douze lignes. Deux indices avancent en parallèle dans les deux suites triées; à chaque tour on compare les deux éléments de tête et on prélève le plus petit.

def fusion(gauche, droite):
    """Fusionne deux listes triees en une seule, en preservant l'ordre d'entree."""
    resultat = []
    i = j = 0
    while i < len(gauche) and j < len(droite):
        if gauche[i] <= droite[j]:       # <= et non < : c'est la stabilite
            resultat.append(gauche[i])
            i += 1
        else:
            resultat.append(droite[j])
            j += 1
    resultat.extend(gauche[i:])          

Le coût de cette fonction se lit sur son texte: chaque tour de la boucle while fait une comparaison et écrit un élément dans le résultat. Une fusion de deux suites de longueurs $p$ et $q$ fait donc au plus $p+q-1$ comparaisons — au plus, car la boucle s'arrête dès qu'un des deux côtés est épuisé, et la queue de l'autre est recopiée sans aucune comparaison. Le minimum est $\min (p,q)$, atteint quand tous les éléments d'un côté précèdent tous ceux de l'autre.

Démonstration. Terminaison. À chaque tour de la boucle, exactement l'un des deux indices $i$ et $j$ augmente d'une unité, donc la quantité $(p-i)+(q-j)$, entière et positive, décroît strictement. La boucle fait donc au plus $p+q$ tours et s'arrête.

Invariant. Nous montrons qu'au début de chaque test de la condition de boucle, la propriété suivante est vraie:

Invariant $J$ — la liste resultat est croissante, elle contient exactement les $i$ premiers éléments de gauche et les $j$ premiers de droite, et tout élément de resultat est inférieur ou égal à gauche[i] s'il existe, et à droite[j] s'il existe.

Initialisation. Au premier test, $i=j=0$ et resultat est vide. Une liste vide est croissante, elle contient bien les zéro premiers éléments de chaque côté, et la dernière clause est vide de sens, donc vraie.

Conservation. Supposons $J$ vraie au début d'un tour et supposons gauche[i] <= droite[j], l'autre cas étant symétrique. Le corps ajoute gauche[i] à la fin de resultat et incrémente $i$. La liste reste croissante: par $J$, tous les éléments déjà présents sont inférieurs ou égaux à gauche[i], donc l'ajouter en queue préserve la croissance. La clause de contenu reste vraie, puisque l'on a ajouté exactement l'élément d'indice $i$ de gauche et incrémenté $i$. Reste la troisième clause. Le nouvel élément de tête à gauche, gauche[i+1], est supérieur ou égal à gauche[i] parce que gauche est croissante; et droite[j] est supérieur ou égal à gauche[i] par l'hypothèse du cas. Tout élément de la nouvelle liste resultat est donc inférieur ou égal à la nouvelle tête de chaque côté: $J$ est vraie au test suivant.

Terminaison de la boucle. La boucle s'arrête lorsque $i=p$ ou $j=q$. Supposons $i=p$, l'autre cas étant symétrique. Par $J$, resultat est croissante, contient tous les éléments de gauche et les $j$ premiers de droite, et chacun de ses éléments est inférieur ou égal à droite[j]. L'instruction resultat.extend(gauche[i:]) n'ajoute rien, puisque la tranche est vide, et resultat.extend(droite[j:]) ajoute la suite $droite[j],droite[j+1],\dots$, croissante, dont le premier terme majore tous les éléments déjà présents. La concaténation d'une liste croissante et d'une liste croissante dont le minimum majore le maximum de la première est croissante: le résultat est donc croissant. Il contient éléments, et le multi-ensemble de ses éléments est la réunion des deux, puisque chaque élément a été ajouté exactement une fois — une fois dans la boucle, ou une fois dans la recopie de queue, jamais les deux, les indices et ne reculant jamais.

Le nombre de comparaisons. Chaque tour de boucle effectue exactement une comparaison et augmente $i+j$ d'une unité. Lorsque la boucle s'arrête, on a $i=p$ ou $j=q$, donc $i+j\le p+q-1$ sauf si les deux côtés sont épuisés simultanément — ce qui est impossible, puisque le tour qui épuise l'un laisse au moins un élément dans l'autre dès que et sont non nuls. Le nombre de tours, donc de comparaisons, vaut . Il vaut au moins , car la boucle ne peut s'arrêter avant d'avoir épuisé le plus court des deux côtés, ce qui demande au moins tours.

Le tableau témoin, fusion par fusion

Le coût exact du tri fusion, et ce qu'il annonce

Le nombre de comparaisons du tri fusion dans le pire des cas se calcule exactement. En notant $M(n)$ ce nombre, la récurrence est

et sa solution close, que l'on vérifie par récurrence, est $M(n)=n\lceil {\log }_{2}n\rceil -2^{\lceil {\log }_{2}n\rceil }+1$. Pour $n=7$ elle donne ; pour , ; pour , . Le tableau témoin, avec ses 13 comparaisons, est donc une comparaison en dessous du pire des cas de sa taille — et nous verrons dans la section sur la borne inférieure que 13 est un nombre remarquable pour .

Le tri fusion est en $\Theta (n\log n)$ comparaisons dans les trois régimes: pire des cas, cas moyen, cas favorable. Sa récurrence ne regarde jamais le contenu du tableau, seulement sa longueur. C'est à la fois sa force — aucune entrée ne le met en difficulté, et un adversaire ne peut rien contre lui — et sa faiblesse, car il ne sait pas profiter d'un tableau presque trié. Son défaut principal est ailleurs: il n'est pas en place. La fusion écrit dans une zone auxiliaire, et l'implémentation courante consomme $\Theta (n)$ mémoire supplémentaire. Sur un million d'enregistrements volumineux, ce n'est pas un détail.

Le tri rapide

L'idée, et la partition de Lomuto

Le tri fusion divise la position — il coupe le tableau en deux moitiés de longueurs égales, sans regarder le contenu — puis fait tout le travail à la remontée, dans la fusion. Le tri rapide fait l'inverse: il divise la valeur, en choisissant un élément appelé pivot et en réarrangeant le tableau de sorte que tout ce qui est à gauche du pivot lui soit inférieur ou égal et tout ce qui est à droite lui soit supérieur. Le pivot est alors à sa place définitive, les deux moitiés se trient récursivement, et il n'y a rien à faire à la remontée.

Plusieurs schémas de partition existent. Celui de ce cours est la partition de Lomuto, avec le dernier élément comme pivot — c'est la variante la plus simple à écrire correctement et à démontrer, et c'est celle de CLRS. Le schéma de Hoare, historiquement antérieur, fait moins d'échanges mais ne place pas le pivot à sa place et demande plus de soin; nous le mentionnons dans les exercices.

def partition(t, lo, hi):
    """Partition de Lomuto autour de t[hi]. Renvoie la position finale du pivot."""
    pivot = t[hi]
    i = lo - 1                       # dernier indice de la zone <= pivot
    for j in range(lo, hi):
        if t[j] <= pivot:
            i += 1
            t[i], t[j] = t[j], t[i]
        # invariant : t[lo..i] <= pivot  et  t[i+1..j] > pivot
    t[i + 1], t[hi] = t[hi], t[i + 1]
    return

Le coût de partition se lit sur son texte: la boucle for fait exactement $hi-lo$ tours, donc une comparaison par tour — c'est la convention du cours — soit $m-1$ comparaisons pour un sous-tableau de $m$ éléments. Elle fait au plus $m-1$ échanges. Le commentaire placé dans la boucle est l'invariant qui démontre la correction de la partition, et c'est l'exercice 3.3.

Lisez la figure 3.2 comme un film. Pendant les trois premiers tours, rien ne bouge: 38, 27 et 43 sont tous supérieurs au pivot, et l'algorithme se contente de les laisser où ils sont — ils sont dans la zone «supérieure au pivot», qui commence à l'indice i + 1 et n'a même pas besoin d'être déplacée. Au quatrième tour, 3 est inférieur au pivot: la zone sur fond teinté doit s'agrandir d'une case, donc i avance et la valeur 3 est échangée avec ce qui occupait cette case, à savoir 38. Le tri rapide déplace chaque petit élément vers la gauche en une seule écriture, là où le tri par insertion le fait remonter case par case: c'est là qu'il gagne.

Le pire des cas: le tableau déjà trié

Le coût du tri rapide dépend entièrement de l'équilibre des partitions. Si chaque pivot coupe le sous-tableau en deux moitiés égales, la récurrence est celle du tri fusion, $T(n)=2T(n/2)+n-1$, et le coût est en $\Theta (n\log n)$. Si au contraire chaque pivot est le maximum — ou le minimum — du sous-tableau, la partition produit un morceau vide et un morceau de $m-1$ éléments, et la récurrence devient

Quand cela arrive-t-il? Précisément lorsque le dernier élément est le plus grand — ou le plus petit — à chaque appel, c'est-à-dire lorsque le tableau est déjà trié, en ordre croissant ou décroissant. Le programme le confirme:

trace_rapide([3, 9, 10, 27, 38, 43, 82])

a[0..6] pivot 82 : 6 comp. -> [3, 9, 10, 27, 38, 43, 82]
a[0..5] pivot 43 : 5 comp. -> [3, 9, 10, 27, 38, 43, 82]
a[0..4] pivot 38 : 4 comp. -> [3, 9, 10, 27, 38, 43, 82]
a[0..3] pivot 27 : 3 comp. -> [3, 9, 10, 27, 38, 43, 82]
a[0..2] pivot 10 : 2 comp. -> [3, 9, 10, 27, 38, 43, 82]
a[0..1] pivot  9 : 1 comp. -> [3, 9, 10, 27, 38, 43, 82]
total : 21 comparaisons

Ce que le pivot aléatoire achète, exactement

La parade est d'ôter à l'adversaire la connaissance du pivot. Une ligne suffit: avant de partitionner, on échange t[hi] avec un élément tiré uniformément dans t[lo..hi].

import random

def partition_aleatoire(t, lo, hi):
    """Choisit le pivot au hasard, puis applique la partition de Lomuto."""
    k = random.randint(lo, hi)
    t[k], t[hi] = t[hi], t[k]
    return partition(t, lo, hi)

Il faut être précis sur ce que ce tirage change et sur ce qu'il ne change pas.

Ce qu'il ne change pas: le pire des cas. Il existe toujours des exécutions en $\Theta (n^2)$ comparaisons — celles où les tirages successifs tombent, par malchance, sur les extrêmes. Aucune entrée n'est à l'abri, et $T_{\max }(n)=\Theta (n^2)$ reste vrai.

Ce qu'il change: l'aléa ne vient plus des données, mais du programme. Avant le tirage, la moyenne était prise sur une loi hypothétique des entrées, que rien ne garantissait et qu'un adversaire pouvait violer. Après, elle est prise sur les tirages de l'algorithme, que l'adversaire ne contrôle pas: pour toute entrée, y compris la pire, le coût moyen est en $\Theta (n\log n)$. On passe d'une hypothèse sur le monde à une garantie sur le programme, et c'est un progrès considérable. C'est la différence entre un algorithme déterministe analysé en moyenne et un algorithme randomisé.

Démonstration (esquisse). La partition d'un sous-tableau de $m$ éléments coûte $m-1$ comparaisons et le pivot tombe en position $k$ avec probabilité $1/m$, pour $k=0,\dots ,m-1$, chacune donnant deux sous-problèmes de tailles $k$ et $m-1-k$. D'où la récurrence

Cette récurrence à histoire complète se résout par la méthode classique: on écrit $n\bar{C}(n)$ et $(n-1)\bar{C}(n-1)$, on soustrait pour éliminer la somme, on obtient $n\bar{C}(n)=(n+1)\bar{C}(n-1)+2(n-1)$, puis on divise par pour faire apparaître une somme télescopique en , dont la sommation donne les nombres harmoniques. Le détail de ce calcul relève du chapitre 2 et des rappels de l'annexe A; il est demandé en exercice. Nous retenons le résultat, et nous le : pour , la formule donne , et l'énumération exhaustive des permutations donne la moyenne exacte . Les deux coïncident au rationnel près.

Le facteur $1,39$ est la rançon du tri rapide: il fait en moyenne 39 % de comparaisons de plus que la borne théorique $n{\log }_{2}n$, et sensiblement plus que le tri fusion. Et pourtant, sur une machine réelle, le tri rapide est le plus rapide des trois. La raison ne se lit pas dans le nombre de comparaisons: il travaille en place, ses accès mémoire sont séquentiels et donc amis du cache, et sa boucle intérieure est d'une brièveté que ni la fusion ni l'insertion n'atteignent. C'est le cas d'école d'un algorithme que l'analyse asymptotique classe second et que les constantes cachées placent premier.

Un tri en cours d'exécution

Avant d'aborder la borne inférieure, prenez le temps de faire tourner les trois tris vous-même sur des tableaux plus longs que sept éléments. L'explorateur ci-dessous les exécute événement par événement — une passe, une fusion, une partition — et affiche les trois totaux en même temps.

Regardez d'abord un tableau aléatoire de 16 éléments: l'insertion en fait 71, la fusion 48, le tri rapide 48. Puis basculez l'état de départ sur déjà trié, sans rien changer d'autre: l'insertion tombe à 15, la fusion reste à 32, et le tri rapide monte à 120, soit $16\times 15/2$. Trois algorithmes, une même entrée, et un renversement complet du classement. Aucun autre affichage de ce chapitre ne dit aussi vite pourquoi la phrase «ce tri est en $n\log n$» est incomplète tant qu'on n'a pas dit dans quel cas.

La borne inférieure des tris par comparaison

Ce qu'un algorithme de tri sait, et comment il l'apprend

Nous avons trois algorithmes dont le meilleur fait $\Theta (n\log n)$ comparaisons. Question naturelle: peut-on faire mieux? Existe-t-il, quelque part, un tri en $\Theta (n)$ comparaisons qui attend d'être trouvé?

La réponse est non, et ce «non» n'est pas un aveu d'ignorance: c'est un théorème. Il porte sur une classe précise d'algorithmes, qu'il faut d'abord définir.

Les trois tris de ce chapitre sont des tris par comparaison, ainsi que le tri par sélection, le tri à bulles, le tri par tas et le Timsort de Python. Cette restriction est aussi une généralité: un tri par comparaison fonctionne sur n'importe quel type muni d'un ordre total, sans rien savoir de sa nature. C'est ce qui permet à sorted de trier des nombres, des chaînes, des tuples et vos propres objets avec le même code.

L'arbre de décision

L'arbre ne dépend pas de l'entrée: il dépend de l'algorithme et de $n$. C'est une représentation de tout ce que l'algorithme peut faire sur toutes les entrées de taille $n$, et c'est ce qui permet de raisonner sur lui sans le connaître.

Deux observations sur la figure 3.3, qui contiennent toute la démonstration à venir.

La première: l'arbre a au moins $n!$ feuilles. Si deux permutations distinctes de l'entrée conduisaient à la même feuille, l'algorithme leur appliquerait la même suite de déplacements et produirait le même réarrangement; or deux entrées d'ordres relatifs différents exigent des réarrangements différents. L'une des deux sorties serait donc fausse. Un tri correct doit distinguer les $n!$ ordres relatifs, et il n'a pour cela que ses comparaisons.

La seconde: un arbre binaire de profondeur $h$ a au plus $2^h$ feuilles. C'est immédiat par récurrence sur $h$: un arbre de profondeur 0 est une feuille, et un arbre de profondeur $h$ est fait d'une racine et de deux sous-arbres de profondeur au plus $h-1$, donc d'au plus $2\times 2^{h-1}=2^h$ feuilles.

Ces deux inégalités se mordent la queue, et c'est le théorème.

Démonstration. Soit $A$ un algorithme de tri par comparaison correct sur toutes les entrées de $n$ éléments deux à deux distincts, et soit ${\mathcal{A}}_n$ son arbre de décision pour cette taille. Notons $F$ son nombre de feuilles et $h$ sa profondeur, c'est-à-dire la longueur du plus long chemin de la racine à une feuille. Par définition de l'arbre de décision, $h$ est exactement le nombre de comparaisons de $A$ dans le pire des cas.

Première étape: $F\ge n!$. Fixons un ensemble de $n$ valeurs deux à deux distinctes et considérons les $n!$ entrées obtenues en les permutant. Chacune conduit l'exécution à une feuille de ${\mathcal{A}}_n$. Supposons par l'absurde que deux entrées distinctes $x$ et $y$ atteignent la même feuille $\ell$. Alors $A$ a effectué sur et sur exactement la même suite de comparaisons et reçu exactement les mêmes réponses; comme un tri par comparaison n'a pas d'autre source d'information sur les valeurs, il a exécuté la même suite d'instructions, donc appliqué le réarrangement des positions — appelons-le , la permutation attachée à la feuille . Or et sont deux permutations distinctes du même ensemble de valeurs: la permutation qui trie n'est pas celle qui trie . L'une au moins des deux sorties , n'est donc pas croissante, ce qui contredit la correction de . Chaque entrée atteint donc une feuille qui lui est propre, et .

Deuxième étape: $F\le 2^h$. Par récurrence sur $h$. Un arbre binaire de profondeur 0 est réduit à une feuille, donc $F=1=2^0$. Soit $h\ge 1$ et supposons la propriété vraie pour toute profondeur strictement inférieure. Un arbre de profondeur $h$ a une racine et au plus deux sous-arbres, chacun de profondeur au plus ; ses feuilles sont exactement celles de ses sous-arbres, donc au plus .

Conclusion. En combinant, $n!\le F\le 2^h$, d'où, le logarithme binaire étant croissant,

Comme $h$ est un entier, $h\ge \lceil {\log }_2(n!)\rceil$, ce qui est la première assertion.

Il reste à en déduire la forme asymptotique. Le théorème 1.3 du chapitre 1 établit ${\log }_2(n!)\in \Theta (n{\log }_{2}n)$, et sa minoration est explicite: en ne gardant que les $\lceil n/2\rceil$ plus grands facteurs de $n!=1\times 2\times \cdots \times n$, chacun au moins égal à , on obtient , donc

la dernière inégalité parce que ${\log }_{2}n\ge 2$ entraîne ${\log }_{2}n-1\ge \frac{1}{2}{\log }_{2}n$. Le couple témoigne donc que le nombre de comparaisons dans le pire des cas appartient à .

Ce que la borne dit, et ce qu'elle ne dit pas

La borne est-elle atteinte? Asymptotiquement oui: le tri fusion fait $n\lceil {\log }_{2}n\rceil -2^{\lceil {\log }_{2}n\rceil }+1$ comparaisons au pire, et le rapport de ce nombre à ${\log }_2(n!)$ tend vers 1. Exactement, non: pour , la borne vaut et le tri fusion en fait 8 au pire; il existe un tri à 7 comparaisons pour cinq éléments, celui de Ford et Johnson, mais il n'est pas optimal pour toutes les tailles et la question du minimum exact reste ouverte au-delà de quelques dizaines d'éléments. Le tableau ci-dessous compare les deux quantités.

Une ligne de ce tableau mérite d'être relue à la lumière de l'exemple 3.1. Pour $n=7$, la borne vaut 13, et le tri fusion sur le tableau témoin fait exactement 13 comparaisons. Sur cette entrée-là, il extrait de chaque comparaison un bit d'information parfaitement utilisé: sept éléments, $5040$ ordres possibles, ${\log }_{2}5040=12,30$, donc 13 comparaisons au minimum pour lever l'ambiguïté — et il en fait 13. Ce n'est pas le cas de toutes ses entrées: son pire cas à cette taille est 14.

Trier en temps linéaire, et à quel prix

La brèche

La borne du théorème 3.4 s'applique aux algorithmes qui ne font que comparer. Un algorithme autorisé à regarder les valeurs — à les utiliser comme indices dans un tableau, par exemple — n'en relève pas, et peut trier en temps linéaire. Il paie ce privilège par une hypothèse sur les données, et toute l'honnêteté de cette section tient à énoncer cette hypothèse aussi clairement que le théorème qu'elle contourne.

Le tri par comptage

Supposons que les $n$ valeurs à trier soient des entiers de l'intervalle $[0,k)$, avec $k$ connu. On peut alors compter combien de fois chaque valeur apparaît, puis reconstruire le tableau trié.

def tri_comptage(a, k):
    """Trie des entiers de [0, k) par comptage. Stable."""
    compte = [0] * k
    for v in a:                          # une passe sur les donnees
        compte[v] += 1
    for i in range(1, k):                # cumuls : compte[i] = nb d'elements <= i
        compte[i] += compte[i - 1]
    sortie = [0] * len(a)

L'algorithme fait zéro comparaison entre éléments. Il fait $n$ incrémentations, $k$ additions de cumul et $n$ écritures, soit $\Theta (n+k)$ opérations. Lorsque $k\in O(n)$ — des notes de 1 à 6, des jours de l'année, des octets —, le coût est $\Theta (n)$, linéaire, et la borne $\Omega (n\log n)$ n'est pas contredite: elle ne parlait pas de cet algorithme.

Le tri par base

Le tri par comptage s'effondre quand $k$ est grand: trier un million d'entiers 32 bits par comptage demanderait un tableau de $2^{32}$ compteurs, soit plus de quatre milliards de cases. Le tri par base (radix sort) résout cela en traitant les nombres chiffre par chiffre, du moins significatif au plus significatif, avec un tri stable à chaque passe.

def tri_base(a, chiffres, base=10):
    """Trie des entiers positifs, un chiffre a la fois, du plus faible au plus fort."""
    t = list(a)
    for p in range(chiffres):
        paquets = [[] for _ in range(base)]
        for v in t:
            paquets[(v // base ** p) % base].append(v)
        t = [v for paquet in paquets 

Le coût du tri par base est $\Theta (d(n+b))$ pour $d$ chiffres en base $b$. Pour un million d'entiers 32 bits traités par tranches de 8 bits, on a $d=4$ et $b=256$, soit environ $4\times (10^6+256)\approx 4,0$ millions d'opérations, contre millions de comparaisons pour un tri par comparaison optimal. Le facteur est réel, et c'est pourquoi le tri par base est employé là où il s'applique: bases de données, tri de clés de longueur fixe, tri sur disque.

Sélectionner sans trier

Le problème du k-ième

Une solution immédiate: trier, puis lire a[k], pour $\Theta (n\log n)$ comparaisons. Est-ce nécessaire? Non, et le cas $k=0$ le montre à lui seul: le minimum s'obtient en $n-1$ comparaisons, et le chapitre 1 a démontré que $n-1$ est optimal. Trier pour trouver le minimum, c'est calculer beaucoup plus que la question posée. La question de cette section est de savoir jusqu'où cette économie s'étend.

Quickselect

L'idée est de reprendre la partition du tri rapide, en observant que l'on sait immédiatement de quel côté se trouve la réponse. Après une partition qui place le pivot à l'indice $p$: si $p=k$, c'est fini; si $p>k$, l'élément cherché est strictement à gauche; sinon il est strictement à droite. On ne récurse donc que d'un seul côté — et c'est toute la différence.

def selection(a, k):
    """Renvoie le k-ieme plus petit element de a (k a partir de 0)."""
    t = list(a)
    lo, hi = 0, len(t) - 1
    while True:
        p = partition(t, lo, hi)     # la partition de Lomuto du tri rapide
        if p == k:
            return t[p]
        if p < k:
            lo = p + 1               # la reponse est strictement a droite
        else

Notez que la boucle while remplace la récursion: comme un seul appel subsiste, la récursion est terminale et s'élimine. L'algorithme travaille en place et n'utilise que $O(1)$ mémoire supplémentaire.

Le coût: linéaire en moyenne

Démonstration. Appelons bon un pivot dont la position $p$ tombe dans le quart central, c'est-à-dire tel que les deux morceaux aient chacun au plus $3m/4$ éléments, où $m$ est la taille du sous-tableau courant. Un pivot tiré uniformément est bon avec probabilité au moins $1/2$, puisque les positions acceptables forment la moitié centrale des $m$ positions possibles.

Une partition coûte $m-1<m$ comparaisons. Le nombre de tirages nécessaires pour obtenir un bon pivot est une variable géométrique de paramètre au moins $1/2$, d'espérance au plus 2: en moyenne, on paie donc au plus $2m$ comparaisons pour faire passer la taille de $m$ à au plus $3m/4$. En notant $\bar{T}(n)$ le coût moyen, il vient

et en déroulant, $\bar{T}(n)\le 2n(1+\frac{3}{4}+(\frac{3}{4}{)}^2+\dots )=2n\cdot \frac{1}{1-3/4}=8n$. Une analyse plus fine, qui tient compte de ce que le sous-problème est en moyenne bien plus petit que , abaisse sensiblement cette constante; nous ne la ferons pas ici, elle relève d'un cours de probabilités, et elle ne change rien à la conclusion: .

Pour le pire des cas, il suffit de reprendre l'entrée qui met en défaut le tri rapide: si chaque pivot est le maximum du sous-tableau et que l'on cherche le minimum, les tailles décroissent de un en un et le coût vaut $(n-1)+(n-2)+\cdots =n(n-1)/2$. $\square$

La différence avec le tri rapide est structurelle et mérite d'être nommée: le tri rapide visite tout l'arbre de récursion, quickselect n'en visite qu'une branche. C'est pourquoi le premier est en $n\log n$ et le second en $n$.

La médiane des médianes: une garantie au pire

Peut-on obtenir $O(n)$ dans le pire des cas, sans aléa? Oui. L'algorithme de Blum, Floyd, Pratt, Rivest et Tarjan (1973) choisit le pivot de façon à garantir qu'il n'est jamais trop excentré, en le calculant par un appel récursif à la sélection elle-même.

Nous ne démontrons pas ce théorème dans le corps du chapitre, et ce n'est pas une facilité: sa démonstration est l'exercice 3.5, guidée pas à pas, parce qu'elle réunit tout ce que le chapitre a introduit — un dénombrement géométrique pour la borne $3n/10-6$, puis une récurrence à deux appels de tailles inégales dont la somme des fractions, $1/5+7/10=9/10<1$, est exactement ce qui la rend linéaire. C'est la seule récurrence de ce cours dont les deux appels ne sont pas de même taille, et comprendre pourquoi $9/10<1$ suffit vaut mieux que lire la démonstration.

Un mot sur son intérêt pratique, parce qu'il est souvent mal présenté: les constantes cachées de la médiane des médianes sont si grandes qu'en pratique on utilise quickselect. L'algorithme sert de pivot de secours: l'introselect des bibliothèques modernes lance quickselect, compte ses tours, et bascule sur la médiane des médianes s'il en fait trop. On obtient le cas moyen de l'un et la garantie au pire de l'autre — la même construction que l'introsort, qui protège le tri rapide en basculant sur le tri par tas.

La stabilité, et quand elle décide

La définition, sur un exemple

Reprenons la définition posée au début du chapitre: un tri est stable s'il ne permute jamais deux éléments de même clé. Sur des nombres nus, la propriété est invisible: deux 5 sont indiscernables. Elle devient visible dès que les éléments portent autre chose que leur clé.

classement = [("Alice", 5.0), ("Bruno", 4.5), ("Chloé", 5.0),
              ("David", 4.5), ("Elena", 6.0)]
print(sorted(classement, key=lambda p: -p[1]))

[('Elena', 6.0), ('Alice', 5.0), ('Chloé', 5.0), ('Bruno', 4.5), ('David', 4.5)]

Alice précède Chloé, et Bruno précède David: à note égale, l'ordre de départ est conservé. Le tri de Python est stable, et cette garantie est documentée, donc utilisable. Un tri instable aurait pu produire Chloé avant Alice, sans être faux pour autant — le résultat resterait décroissant par note.

Le tri à deux clés, qui est l'usage principal

La stabilité n'est pas une élégance: c'est un mécanisme de composition. Elle permet de trier selon plusieurs critères en les appliquant l'un après l'autre, du moins important au plus important.

# On veut : par note decroissante, et a note egale par ordre alphabetique.
par_nom = sorted(classement, key=lambda p: p[0])          # critere secondaire
final = sorted(par_nom, key=lambda p: -p[1])              # critere principal
print(final)

[('Elena', 6.0), ('Alice', 5.0), ('Chloé', 5.0), ('Bruno', 4.5), ('David', 4.5)]

Le second tri respecte l'ordre alphabétique établi par le premier à l'intérieur de chaque groupe de note égale, parce qu'il est stable. Sans stabilité, il faudrait écrire une clé composite — ce qui reste possible ici, mais devient pénible dès que les sens de tri diffèrent d'un critère à l'autre, ou que les critères sont décidés à l'exécution par l'utilisateur d'une interface. Un tableau de bord dont l'utilisateur clique successivement sur trois colonnes repose entièrement sur cette propriété.

Et nous en avons déjà vu un usage où la stabilité n'est pas un confort mais une condition de correction: le tri par base de l'exemple 3.4 est faux si ses passes ne sont pas stables. C'est le meilleur argument en faveur de cette notion, et le moins connu.

Quels tris sont stables

Trois lignes à commenter. Le tri par insertion est stable parce que sa boucle intérieure s'arrête sur t[j] <= valeur, donc ne fait jamais passer un élément devant un égal; le remplacer par t[j] < valeur le rendrait instable et sensiblement plus lent sur les données à doublons. Le tri par sélection est instable pour une raison structurelle: il échange le minimum avec la première case non triée, et cet échange saute par-dessus tout ce qui sépare les deux positions. Le tri rapide est instable pour la même raison: la partition de Lomuto échange t[i] et t[j], deux cases arbitrairement éloignées.

Rendre un tri instable stable est toujours possible et jamais gratuit: il suffit d'adjoindre à chaque élément son indice d'origine et de comparer les paires lexicographiquement, ce qui coûte $\Theta (n)$ mémoire supplémentaire. Si vous avez besoin de stabilité et de travailler en place, vous n'avez pas d'algorithme simple à proposer, et c'est un vrai problème de recherche.

Le tri par tas, annoncé et chiffré

Il manque un tri au tableau ci-dessus, et c'est celui qui réunit les deux qualités que les autres se partagent: $\Theta (n\log n)$ comparaisons dans le pire des cas et travail en place. Le tri par tas (heapsort) construit sur le tableau une structure d'arbre implicite appelée tas, dans laquelle chaque nœud est supérieur ou égal à ses deux fils, puis extrait le maximum $n$ fois.

Nous ne le développons pas ici: la structure de tas, l'opération sift_down qui la rétablit et la construction de Floyd en temps linéaire appartiennent au chapitre 5, qui les démontre. Ce chapitre se borne à annoncer les coûts, à titre de repères pour le tableau comparatif:

• construire un tas sur $n$ éléments coûte $\Theta (n)$ opérations par l'algorithme de Floyd — et non $\Theta (n\log n)$, ce qui est contre-intuitif et fera l'objet d'une démonstration au chapitre 5;
• chaque extraction du maximum coûte $O(\log n)$ comparaisons, puisqu'elle fait descendre un élément d'une hauteur au plus $\lfloor {\log }_{2}n\rfloor$;
• le tri complet coûte donc $\Theta (n)+n\cdot O(\log n)=\Theta (n\log n)$ comparaisons , en mémoire supplémentaire.

Sur le tas témoin du cours, obtenu en tassant le tableau témoin par l'algorithme de Floyd, le min-tas vaut [3, 9, 10, 27, 38, 82, 43] et le max-tas [82, 27, 43, 3, 9, 38, 10]; le chapitre 5 les construit pas à pas.

Pourquoi ce tri, qui a les meilleures garanties du lot, n'est-il pas celui des bibliothèques? Parce que ses accès mémoire sautent d'un indice $i$ à $2i+1$ et $2i+2$, donc à travers tout le tableau, ce qui est le pire comportement possible vis-à-vis du cache. Sa constante cachée est nettement plus grande que celle du tri rapide. Il sert, comme dit plus haut, de filet de sécurité: l'introsort de la bibliothèque standard de C++ lance un tri rapide et bascule sur le tri par tas quand la profondeur de récursion dépasse $2{\log }_{2}n$, ce qui lui donne le cas moyen du premier et le pire des cas du second.

Synthèse

• Trier, c'est produire une permutation croissante de l'entrée: la seconde exigence est celle qu'on oublie de tester. Un tri se décrit par trois adjectifs indépendants de sa classe de complexité — en place, stable, adaptatif — et ce sont eux qui décident le plus souvent en pratique. L'opération barométrique est la comparaison entre deux éléments, et ce cours dit toujours ce qu'il compte: une comparaison par test entre deux éléments, y compris celui qui sort de la boucle, une par tour de la boucle de fusion, une par tour de la boucle de partition.
• Le tri par insertion est correct par un invariant de boucle en deux clauses — préfixe croissant et préfixe contenant les bons éléments. Il fait $n-1$ comparaisons dans le cas favorable, $n(n-1)/2$ dans le pire des cas et $n(n-1)/4+n-H_n$ en moyenne sous la loi uniforme des permutations, soit pour . Sur le tableau témoin: . Il est stable, en place et adaptatif, ce qui lui vaut d'être employé par toutes les bibliothèques sur les fragments courts.

Exercices

Vous pouvez afficher le corrigé directement sous chaque énoncé après avoir cherché la solution.

Références

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, 4ᵉ éd., MIT Press — chapitre 2 pour le tri par insertion et son invariant, chapitre 7 pour le tri rapide et son analyse en moyenne, chapitre 8 pour la borne inférieure et les tris en temps linéaire, chapitre 9 pour la sélection et la médiane des médianes.
• Cormen, Leiserson, Rivest & Stein, Algorithmique, 3ᵉ éd., Dunod — la traduction française des mêmes chapitres, utile pour fixer le vocabulaire: partition, pivot, arbre de décision, tri par dénombrement.
• Sedgewick & Wayne, Algorithms, 4ᵉ éd., Addison-Wesley — chapitre 2, «Sorting», pour les variantes pratiques du tri rapide (pivot médian de trois, partition à trois voies pour les clés répétées) et la discussion de la stabilité.
• Kleinberg & Tardos, Algorithm Design, Pearson — chapitre 5, pour le tri fusion vu comme schéma «diviser pour régner» et le comptage des inversions, qui est le lien avec le caractère adaptatif du tri par insertion.
• Blum, Floyd, Pratt, Rivest & Tarjan, «Time Bounds for Selection», Journal of Computer and System Sciences, vol. 7, 1973 — l'article d'origine de la médiane des médianes.
• Knuth, The Art of Computer Programming, vol. 3, Sorting and Searching, 2ᵉ éd., Addison-Wesley — pour un point précis: la section 5.3.1 traite du nombre minimal de comparaisons et de l'algorithme de Ford et Johnson.