Introduction.

L'algorithme du tri rapide est très certainement l'un des algorithmes les plus célèbres et les plus étu­diés. Il a été conçu en 1961 par l'informaticien britannique Charles Hoare qui est également à l'ori­gine, entre autres, de la logique qui porte son nom et qui est utilisée en preuve de programmes (cours de troisième année). Paradoxalement la complexité dans le pire des cas de ce tri n'est pas linéarithmique mais quadratique. Cependant les cas dévaforables sont peu fréquents et sa complexité moyenne est linéarithmique avec un coefficient caché meilleur que ceux des autres algorithmes de tri dans la même classe de complexité. Il existe désormais de nombreuses déclinaisons de cet algorithme avec les corrections nécessaires pour que la complexité reste linéarithmique dans le pire des cas.

À l'instar du tri fusion, le tri rapide est un tri qui utilise le principe diviser pour régner pour trier les \(n\) entiers d'une liste indexée de \(1\) à \(n\). À chaque étape, la sous-liste \(L[p\!:\!r]\) est partitionnée en deux sous-listes gauche \(L[p\!:\!q]\) et droite \(L[q+1\!:\!r]\), mais cette fois la césure en \(q\) ne se fait plus né­ces­sai­re­ment au milieu \((p+r)/2\) de la liste. Il en résulte un déséquilibre possible entre les tailles des deux sous-­listes et si ce choix peut paraître étrange a priori, il se fait au bénéfice d'une propriété obtenue pendant la phase de partitionnement qui rend inutile l'opération de fusionnement au retour des appels récursifs. En effet, à l'issue du partitionnement, tout élément de la sous-liste \(L[p\!:\!q]\) est inférieur à tout élément de la sous-liste droite \(L[q+1\!:\!r]\), i.e.

propriété que l'on résume par

Comme le tri se fait sur place, s'il opère récursivement sur ces deux sous-listes, il est clair que le simple retour des appels récursifs suffit à achever le travail. La propriété \((\ref{eq:proptr})\) est obtenue en dé­pla­çant des valeurs dans la liste pendant la phase de par­ti­tion­ne­ment qui ne se limite donc pas à dé­ter­mi­ner la position de césure \(q\). Le travail du tri rapide se résume donc essentiellement aux manipulations réalisées pour obtenir le partionnement de la liste \(L\) qui fixe la valeur \(q\).

Le principe du partitionnement est relativement simple, il consiste à ranger les éléments de la sous-liste \(L[p\!:\!r]\) inférieurs ou égaux à une valeur \(x\) appelée pivot dans la partie gauche et les éléments supé­rieurs ou égaux — et on s'attend à un inférieur strict ici, mais il s'agit bien à nouveau d'une inégalité large — dans la partie droite. Le choix de la valeur pivot a fait l'objet de nombreuses études et de déclinaisons de l'algorithme mais nous étudierons ici la version originale dans laquelle la valeur pivot est fixée à \(L[p]\), soit à la valeur contenue dans la première cellule de la sous-liste à partitionner. La valeur de césure \(q\) n'est obtenue qu'après ce travail.

Tri-Rapide(@L,p,r)
données
   L: liste de valeurs
   p, r: entiers
variables
   q: entier
DEBUT
   SI (p < r)
      q ← Partitionner(L,p,r)
      Tri-Rapide(L,p,q)
      Tri-Rapide(L,q + 1,r)
   FSI
FIN

La structure de l'algorithme principal récursif est donc très similaire de celle du tri fusion avec l'absence d'appel à un algorithme de fusionnement rendu inutile grâce à la propriété \((\ref{eq:proptr})\).

Le partitionnement

La partition \(\ab{p}{r}=\ab{p}{q}\sqcup\ab{q+1}{r}\) est construite en fonction du pivot \(x:=L[p]\) en faisant croître les deux régions gauche \(\ab{p}{\color{#FF8}i}\) et droite \(\ab{\color{#F44}j}{r}\) initialement vides (au départ \({\color{#FF8}i}\leftarrow p\), \({\color{#F44}j}\leftarrow r\)) en incrémentant et en décrémentant res­pecti­ve­ment les indices \(i\) et \(j\) jusqu'au point de rencontre qui est précisément le point de césure \(q\) de l'intervalle. On peut visualiser le processus en imaginant que \(i\) et \(j\) sont deux sentinelles qui partent des extrémités opposées de la sous-liste \(L[p\!:\!r]\) et parcourent ses éléments en s'échangeant les valeurs rencontrées à chaque fois qu'elles ne sont pas du bon côté par rapport à la valeur pivot \(x\).

À chaque étape, exceptée la dernière, les deux régions \(\ab{p}{\color{#FF8}i}\) et \(\ab{\color{#F44}j}{r}\) sont telles que les éléments de \(L[p\!:\!i]\) sont tous inférieurs ou égaux au pivot \(x\) et ceux de \(L[j\!:\!r]\) sont tous supérieurs ou égaux au pivot \(x\). Pour mieux mettre en évidence le fonctionnement de l'algorithme on s'appuie sur deux algorithmes auxiliaires pour déplacer les sentinelles. L'initialisation de \(j\) à \(r+1\) au lieu de \(r\) tient au fait qu'elle est suivie par un premier appel à l'algorithme Reculer qui la décrémente une première fois.

Reculer(L,x,@j)              ALGORITHME Avancer(L,x,@i)
données                                 données
   L: liste de valeurs                     L: liste de valeurs
   x: valeur                               x: valeur
   j: entier                               i: entier
debut                                   debut          
   j ← j - 1                               i ← i + 1                    
   TQ (L[j] > x) FAIRE                     TQ (L[i] < x) FAIRE
      j ← j - 1                               i ← i + 1
   FTQ                                     FTQ
fin                                     FIN 

Partitionner(@L,p,r):entier
données
   L: liste de valeurs
   p,r: entiers
variables
   i,j,x: entiers
DEBUT
   x ← L[p]
   i ← p
   j ← r + 1
   Reculer(L,x,j)
   TQ (i < j) FAIRE
      Echanger(L,i,j)
      Reculer(L,x,j)
      Avancer(L,x,i)
   FTQ
   renvoyer(j)
FIN

Montrons que le tri fonctionne. Pour cela, assurons nous tout d'abord que l'algorithme de par­ti­tion­ne­ment est correct en montrant les trois propositions ci-dessous :

(1) Les indices \(i\) et \(j\) appartiennent à l'intervalle \(\ab{p}{r}\) à chaque passage dans la boucle #14.
(2) L'algorithme crée bien une partition, autrement dit \(q\) n'est jamais égal à \(r\).
(3) À l'issue de l'exécution la propriété \((\ref{eq:proptr})\) est bien satisfaite.

(1) Après avoir initialisé le pivot \(x\) et les sentinelles \(i\) et \(j\) en #8, #9 et #10, la boucle #11 a pour objectif de décrémenter \(j\) jusqu'à atteindre la première valeur \(L[j]\) inférieure ou égale à \(x\). Le premier échange effectué dans la boucle principale #14 se fait entre ces dexu valeurs. Avant l'entrée dans la boucle principale #14, vérifions que l'assertion suivante est satisfaite :

En effet, avant la boucle #11, \(i:=p\) puis \(j\) décroit jusqu'à ce que l'on atteigne une valeur \(\leq x\), donc jusqu'à \(i\) au pire puisque \(L[i]=x\), sinon on permute les deux termes et à nouveau \(L[j]=x\). Si l'on n'entre pas dans la boucle principale #14, on a nécessairement \(i=j=p\) et nous avons terminé, sinon la valeur pivot est placée en position \(j\) et on a la nouvelle assertion

Puisque l'on est entré dans la boucle #14, on a \(p < j\) et les instructions \(j\leftarrow j-1\) et \(\ i\leftarrow i+1\) sont exécutées au moins une fois (ligne #09 des deux algorithmes Avancer et Reculer), on a toujours \(p\leq j\) et \(i\leq r\). Les nombres d'incréments et de décréments des variables \(i\) et \(j\) ne dépendent que du pivot \(x\), et comme \(L[p]\leq x\) et \(x\leq L[r]\), cela assure que \(i\) et \(j\) ne sortiront jamais de l'intervalle \([p:r]\).

(2) Il est très facile de vérifier que quelle que soit la situation, la variable \(j\) est décrémentée au moins une fois, donc \(j < r\) à la fin de l'exécution puisqu'elle est initialisée à \(r\) ce qui assure qu'à la sortie de l'algorithme, on n'a jamais \(q=r\) (on rappelle que la valeur renvoyée pour \(q\) est celle de \(j\)).

(3) Il nous reste à prouver que la partition respecte bien la condition (\ref{eq:proptr}). Il est facile de voir que tant que \(i < j\), la variable \(j\) (resp. \(i\)) est toujours décrémentée (resp. incrémentée) jusqu'à ce que \(L[j]\leq x\) (resp. \(L[i]\geq x\)), mais dans ce cas on fait une permutation avec un élément supérieur (resp. inférieur) à \(x\).

Maintenant que nous avons montré que l'algorithme de partitionnement est juste, il est très simple de montrer que l'algorithme Tri-Rapide est juste, il faut pour cela prouver que l'on a l'assertion sui­van­te à l'issue du tri :

Considérons donc \(i\) et \(j\) deux entiers de l'intervalle \([p:r]\) tels que \(i\leq j\). Si \(i\) et \(j\) appartiennent res­pec­ti­ve­ment aux sous-listes gauche et droite du premier partitionnement, alors la propriété est vérifiée, sinon ils appartiennent à la sous-liste \(L[p_1\!:\!r_1]\) avec \(p_1=p\) et \(r_1=q\) s'il s'agit de la sous-liste gauche et \(p_1=q+1\) et \(r_1=r\) sinon. On répète le même raisonnement sur la sous-liste \(L[p_1\!:\!r_1]\) en définissant \(p_2\) et \(r_2\) de la même façon et ainsi de suite. D'autre part, à l'issue du premier par­ti­tion­ne­ment, tous les termes de la liste gauche sont inférieurs aux termes de la liste droite par construction. Il est évident que toute permutation des termes à l'intérieur de chaque sous-liste ne modifie pas cette propriété.

Le tri rapide n'est pas stable. En effet, considérons la liste \([1,2,1,3]\) où le pivot est \(x=1\). La première boucle #11 décrémente \(j\) de la valeur \(4\) à la valeur \(3\) et un échange (instruction #15) aura lieu entre la valeur en position \(1\) et en position \(3\) modifiant ainsi la position respective des deux valeurs \(1\).

Complexité.

Nous allons conclure l'étude du tri rapide par le calcul de la complexité dans le meilleur des cas, dans le pire des cas et enfin dans le cas moyen. On suppose comme à l'ac­cou­tumée que la liste \(L\) de \(n\) valeurs à trier est une permutation de \({\mathfrak S}_n\).

La complexité de l'algorithme de partitionnement sur une liste de taille \(n\) est \(\Theta(n)\). En effet, l'indice \(i\) est incrémenté et l'indice \(j\) est décrémenté jusqu'à ce que \(j=i\), s'ils se rencontrent en \(x\) le pivot, ou \(j=i-1\) sinon. La longueur du chemin total par­cou­ru par les deux indices est donc \(n-1\) ou \(n\).

Concentrons nous maintenant sur le tri. Au premier appel sur la liste \(L\), l'algorithme Tri-Rapide contient deux appels récursifs, le premier traite la sous-liste gauche \(L[1\!:\!q]\) le second la sous-liste droite \(L[q+1\!:\!n]\) qui ont respectivement un coût \(T(q)\) et \(T(n-q)\). D'autre part, nous venons de voir que le partitionnement avait un coût \(\Theta(n)\). L'expression récurrente de la complexité du tri rapide est donc

Le cas défavorable est celui où l'algorithme de partitionnement sépare systématiquement la liste en deux parties totalement déséquilibrées, à savoir en renvoyant \(q=1\) ou encore \(q=n-1\), et ainsi l'une des deux sous-listes est réduite à un unique élément. Il suffit de remplacer \(q\) par \(1\) dans \((\ref{eq:trirapgen})\) et de résoudre la récurrence en notant que \(T(1)=\Theta(1)\) pour obtenir

Le cas favorable est celui où l'algorithme Partitionner renvoie des parties équilibrées de tailles \(\lfloor n/2\rfloor\), on remplace donc \(q\) par \(\lfloor n/2\rfloor\) dans \((\ref{eq:trirapgen})\) et la récurrence devient \(\check T(n)=2\check T(\lfloor n/2\rfloor)+\Theta(n).\) On retrouve ici le même calcul que celui réalisé pour l'analyse du tri fusion et qui fournit :

L'analyse en moyenne du tri rapide dépend essentiellement de l'analyse de l'algorithme de par­ti­tion­ne­ment et il nous faut classer les \(n!\) instances possibles en fonction du nombre d'opérations qui leurs sont appliquées par l'algorithme de partitionnement. D'après l'expression \((\ref{eq:trirapgen})\), c'est la valeur de \(q\) qui fixe le nombre de comparaisons et on sait depuis l'analyse de la justesse de l'algorithme de partitionnement que ni la région gauche \([p,q]\), ni la région droite \([q+1,r]\) n'est vide soit \(q\in[r,p-1]\). Il y a donc exactement \(p-r\) classes d'instances à considérer (soit \(n-1\) pour la liste initiale \(L\)), une pour chaque valeur de \(q\) possible. Plutôt que de dénombrer chacune de ces classes, on va calculer les probabilités \(\text{Pr}(\{q=i\})\) pour \(i\in\ab{1}{n-1}\). Nous allons d'abord faire le lien entre la valeur de \(q\) renvoyée par l'algorithme de partitionnement et le rang du pivot \(x\), c'est-à-dire sa position dans la liste si elle était trié~:

Par construction, une fois le partitionnement achevé, tous les éléments de la sous-liste gauche \(L[p\!:\!q]\) (resp. droite \(L[q+1\!:\!r]\)) sont inférieurs ou égaux (resp. supérieurs ou égaux) à la valeur pivot \(x=L[1]\). La valeur de \(q\) ne dépend donc que de la valeur \(\text{rang}_{\;L}(x)\) du pivot dans la liste \(L\).

On rappelle que \(q\) prend la valeur de la sentinelle \(j\) renvoyée à l'issue du par­ti­tion­ne­ment. Calculons la probabilité des évènements \(\{q=i\}\) pour \(i\in\ab{1}{n-1}\) en distinguant deux cas de figure :

1. Supposons que \(\text{rang}_{\;L}(x)=1\), autrement dit que le pivot est la plus petite valeur dans la liste. Comme elle est en position 1, la première boucle #11 décrémente la valeur de la sentinelle \(j\) jusqu'à la valeur \(i=1\). Donc \(j=1\) à la fin du partitionnement.
2. Supposons que \(k:=\text{rang}_{\;L}(x)>1\). Par définition ceci signifie qu'il y a \(k-1\) entiers stric­tement inférieurs à \(x\). La première boucle #11 décrémente donc \(j\) jusqu'à une valeur strictement supérieure à \(1\) donc strictement supérieure à \(1\) puisque \(i\) est initialisé à \(1\). Comme \(j > i\), on permute le pivot \(x\) en position \(j\) et \(j\) est décrémentée au moins une fois. Comme le pivot \(x\) est désormais à sa position définitive dans la liste, l'indice \(j\) restera toujours strictement inférieur à l'indice du pivot \(x\) qui est dans la sous-liste de droite. Par conséquent la sous-liste de gauche contient exactement les \(k-1\) valeurs strictement inférieures à \(x\) ce qui prouve que \(j=k-1\) à la fin du partitionnement.

Résumons les deux situations. L'algorithme Partitionner renvoie la valeur \(1\) quand \(\text{rang}(x)=1\), et la valeur \(\text{rang}_{\;L}(x)-1\) quand \(\text{rang}_{\;L}(x) > 1\). Si la distribution des permutations suit la loi uniforme, la première entrée de la liste peut contenir n'importe quelle valeur entre \(1\) et \(n\) avec la même probabilité, soit

Nous pouvons maintenant intégrer tous ces calculs dans (\ref{eq:trirapgen}) (rappelée ci-dessous) pour obtenir

L'analyse du tri rapide dans le pire des cas nous permet d'écrire que

or \({\color{#FF8}O(n)}+{\color{#88F}\Theta(n)}=\Theta(n)\). D'autre part, dans la sommation, chaque terme \(\bar T(q)\) apparaît deux fois, donc (\ref{eqtr}) devient

La méthode de substitution devient très vite inextricable avec une équation de ce type. Un peu d'intuition nous fait penser que cette complexité moyenne est en \(O(n\log n)\), nous allons donc mon­trer par récurrence forte que \(\bar T(n)\leq an\log n +b\) pour deux constantes \(a\) et \(b\) à déterminer. Le prédicat \(P(n)\) est donc \(\bar T(n)\leq an\log n +b\). On va donc montrer que

1. \(P(1)\) vrai.
2. \(\forall n\in {\N}\ \ \left(\forall q\in\ab{1}{n-1}\ P(q)\right)\Rightarrow P(n).\)

Le théorème d'approximation par une intégrale nous permet de majorer la sommation par

et une intégration par parties nous montre que la primitive de \(x\log x\) est \(\frac{1}{2}x^2(\log x-\frac{1}{2})\), on obtient donc

En réinjectant ce résultat dans la dernière inégalité, on a

Mais pour \(a\) et \(b\) assez grands, \(\Theta(n)+a+b-\frac{an}{2}\leq 0\) et on peut alors majorer la dernière expression par \(an\log n+b\) ce qui achève la démonstration.

Travaux pratiques

typedef struct {
  uint n;        // longueur de la liste
  int *valeurs;
} tliste;