Tri rapide

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 les autres algorithmes de même complexité. Il existe désormais de nombreuses déclinaisons de cet algorithme qui corrigent ce défaut et ont donc une complexité 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'un tableau indexé de \(1\) à \(n\). Le tableau \(L[p,r]\) est là encore partitionné en deux sous-tableaux \(L[p,q]\) et \(L[q+1,r]\), mais cette fois la valeur \(q\) n'est plus nécessairement égale au milieu \((p+r)/2\). Il en résulte un déséquilibre possible entre les tailles des deux sous-tableaux 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, tous les éléments du sous-tableau gauche \(L[p,q]\) sont inférieurs à tous les éléments du sous-tableau droit \(L[q+1,r]\), i.e.

\begin{equation} \label{eq:proptr} \forall (i,j)\in[p,q]\times[q+1,r],\quad L[i] \leq L[j]. \end{equation}

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

\begin{equation*} L[p:q]\leq L[q+1:r]. \end{equation*}

Comme le tri se fait in situ, si le tri opère récursivement sur ces deux sous-tableaux, 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 le tableau pendant la phase de par­ti­tion­ne­ment qui ne 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 du tableau \(L\) qui fixe la valeur \(q\). La méthode de partitionnement consiste à ranger les éléments du tableau \(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 (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 original mais nous étudierons ici la version originale dans laquelle la valeur pivot est fixée à \(L[p]\), soit la première cellule du sous-tableau à partitionner. La valeur de césure \(q\) n'est obtenue qu'après ce travail.

Tri-Rapide(@L,p,r)
données
   L: tableau de valeurs
   p, r: entiers
variables
   q: entier
DEBUT
   SI (p < r)
      q ← Partitionner(L,p,r)
      Tri-fusion(L,p,q)
      Tri-fusion(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 se construit autour de la valeur pivot \(x:=L[p]\) en faisant croître deux régions \([p,i]\) et \([j,r]\) initialement vides (au départ \(i\leftarrow p\), \(j\leftarrow r\)) en incrémentant et en décrémentant res­pecti­ve­ment les indices \(i\) et \(j\). On peut illustrer le processus en imaginant que \(i\) et \(j\) sont deux sentinelles qui partent des extrémités opposées du tableau \(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. À chaque étape, exceptée la dernière, les deux régions sont telles que les éléments de \(L[p,i]\) sont tous inférieurs ou égaux au pivot et ceux de \(L[j,r]\) sont tous supérieurs ou égaux au pivot.

Partitionner(@L,p,r)
données
   L: tableau de valeurs
   p,r: entiers
variables
   i,j,x: entiers
DEBUT
   x ← L[p]
   i ← p
   j ← r
   TQ (L[j] > x) FAIRE
      j ← j - 1
   FTQ
   TQ (i < j) FAIRE
      Echanger(L,i,j)
      RPT 
         j ← j - 1   
      JQ (L[j] ≤ x)
      RPT 
         i ← i + 1   
      JQ (L[i] ≥ x)
   FTQ
   retourner(j)
FIN

Vous pouvez observer ci-dessous la trace de l'exécution de l'algorithme Partitionner pour la liste \(L=\) que vous pouvez modifier à votre guise. Chaque ligne de la table représente une étape de l'algorithme. Le pivot est encadré en bleu, la sentinelle \(i\) est sur fond jaune, la sentinelle \(j\) sur fond rouge et les deux sur fond orange elles sont égales.

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 trois assertions :

    (1) Les indices \(i\) et \(j\) appartiennent à l'intervalle \([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) La première boucle est un prétraitement qui a pour objectif de ramener \(j\) jusqu'à la première valeur du sous-tableau droit qu'il va falloir échanger avec une valeur du sous-tableau gauche. Les déplacements ultérieurs de \(i\) et \(j\) sont gérés dans la boucle principale #14. Avant l'entrée dans cette boucle, il est aisé de vérifier que l'assertion suivante est satisfaite si l'on note \(x\) le pivot :

\begin{equation*} \label{assert} i=p,\ i\leq j\leq r,\quad L[p:i]\leq x\leq L[j+1:r]. \end{equation*}

En effet, avant la boucle \(i=p\) et \(j\) décroit au pire jusqu'à l'indice \(p\), c'est-à-dire \(i\), dans ce cas \(L[j]=x\) et dans l'autre cas on permute les deux termes et à nouveau \(L[j]=x\). Si l'on n'entre pas dans la boucle principale 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

\begin{equation} i=p,\ i < j\leq r,\quad L[p,i]\leq x\leq L[j,r]\ \text{et}\ L[j]=x. \end{equation}

Puisque l'on est entré dans la boucle, on a \(p < j\) et après l'exécution des deux instructions \(j\leftarrow j-1\) et \(\ i\leftarrow i+1\), (#17 et #20, qui sont exécutées au moins une fois) 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\).

Montrez que quand on sort de la boucle principale, on a toujours \(j=i\) ou \(j=i-1\). Montrez que la situation \(i=j\) ne se produit que quand \(L[j]=x\) si \(x\) désigne le pivot.

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 :

\begin{equation*} \forall i,j,\ p\leq i\leq j\leq r,\quad L[i]\leq L[j]. \end{equation*}

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-tableaux gauche et droite du premier partitionnement, alors la propriété est vérifiée, sinon ils appartiennent au tableau \(L[p_1,r_1]\) avec \(p_1=p\) et \(r_1=q\) s'il s'agit du sous-tableau gauche et \(p_1=q+1\) et \(r_1=r\) sinon. On répète le même raisonnement sur le tableau \(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 du tableau de gauche sont inférieurs aux termes du tableau de droite par construction. Il est évident que toute permutation des termes à l'intérieur de chaque sous-tableau ne modifie pas cette propriété.

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. La complexité de l'algorithme de partitionnement sur un tableau 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 \(i=j\) s'ils se rencontrent sur le pivot, ou \(j=i-1\) sinon. La longueur du chemin total parcouru par les deux indices est donc \(n\) ou \(n+1\).

Concentrons nous maintenant sur le tri. Au premier appel sur le tableau \(L[1,n]\), l'algorithme Tri-Rapide contient deux appels récursifs, le premier traitant le tableau de gauche \(L[1,q]\) le second le tableau de 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é est donc donnée par

\begin{equation} \label{eq:trirapgen} T(n)=T(q)+T(n-q)+\Theta(n). \end{equation}

Le cas défavorable est celui où l'algorithme de partitionnement sépare systématiquement le tableau en deux parties totalement déséquilibrées, à savoir en renvoyant \(q=1\) ou encore \(q=n-1\) et ainsi l'un des deux tableaux est réduit à 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)\), on obtient

\begin{equation*} \hat T(n)=\Theta(n^2). \end{equation*}

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

\begin{equation*} \check T(n)=\Theta(n\log n). \end{equation*}

L'analyse en moyenne du tri rapide dépend essentiellement de l'analyse de l'algorithme de par­ti­tion­ne­ment. On suppose comme toujours que le tableau de \(n\) valeurs à trier est une permutation de \({\mathfrak S}_n\) et il nous faut partitionner (au sens ensembliste mathématique) les \(n!\) tableaux possibles selon le nombre d'opérations nécessaires à réaliser leur partitionnement (au sens de l'algorithme de par­ti­tion­ne­ment du tri rapide).

On appelle rang d'un élément \(x\) d'une liste de valeurs sur un ensemble totalement ordonné, le nombre de termes inférieurs ou égaux à \(x\) dans cette liste.

Par construction, la valeur de \(q\) retournée par l'algorithme Partitionner ne dépend que du rang du pivot \(x=L[1]\). Pour simplifier l'analyse nous allons supposer que le tableau à trier contient une permutation des \(n\) premiers entiers non-nuls. Si la distribution des permutations suit la loi uniforme, il est facile de vérifier que la première entrée du tableau peut contenir n'importe quelle valeur entre \(1\) et \(n\) avec la même probabilité, soit

\[\forall i\in[1,n],\quad \text{Pr}\{\text{rang}(x)=i\}=\frac{1}{n}.\]

Calculons maintenant la probabilité des évènements \(\{q=i\}\), pour \(i\in[1,n-1]\) en distinguant deux cas de figure :

(a) Soit \(k:=\text{rang}(x)=1\). Alors le seul entier inférieur ou égal à \(1\) est \(1\) lui-même et l'indice \(i\) qui valait \(1\) ne change pas alors que l'indice \(j\) est décrémenté jusqu'à \(1\). On a donc montré que \(\text{Pr}\{q=1\;|\;\text{rang}(x)=1\}=1/n\).

(b) Soit \(k:=\text{rang}(x)>1\). Nous allons montrer que la dernière valeur atteinte par l'indice \(j\) est exactement \(k-1\), c'est donc la valeur qui va être renvoyée par Partitionner (l'exemple interactif fourni permet de suivre le raisonnement). Il y a exactement \(k\) entiers inférieurs à \(x\), ou encore \(k-1\) entiers strictement inférieurs à \(x\). La boucle #11 décrémente donc \(j\) jusqu'à une valeur strictement supérieure à \(1\), la valeur initiale de \(i\). Comme \(j>i\), on permute le pivot \(x=L[1]\) en position \(j\) et \(j\) est décrémentée au moins une fois. Comme le pivot \(x\) ne peut plus être déplacé, l'indice \(j\) restera toujours strictement inférieur à l'indice du pivot. La valeur de \(q\) renvoyée par l'algorithme Partitionner est la dernière valeur de \(j\) et on sait que \(L[1,q]\leq x\). Cette partie ne peut pas contenir le pivot \(x\) puisque dans ce cas l'indice \(j\) serait supérieur ou égal à l'indice du pivot et nous venons de voir que ceci n'est pas possible, elle ne contient donc que les \(k-1\) entiers strictement inférieurs à \(x\) ce qui prouve que \(j=k-1\). Nous venons donc de montrer que si \(k:=\text{rang}(x)>1\), alors \(q=k-1\).

Résumons les deux situations \((a)\) et \((b)\). Quand \(\text{rang}(x)=1\), Partitionner renvoie la valeur \(q=1\), et quand \(n-1\geq k:=\text{rang}(x)\geq 2\), Partitionner renvoie la valeur \(q=k-1\). Comme la distribution des différents rangs possibles du pivot est uniforme, la valeur \(q=1\) a deux fois plus de chances d'arriver que les autres valeurs, on a ainsi

\begin{equation} \text{Pr}\{q=1\}=\frac{2}{n}\quad\text{et} \quad\text{Pr}\{q=k-1\}=\frac{1}{n},\ \text{si}\ 2 < k\leq n. \end{equation}

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

\begin{equation}\label{eqtr} \bar T(n)=\frac{1}{n}\big(\bar T(1)+\bar T(n-1)\big)+\frac{1}{n}\sum_{k=1}^{n-1}\Big(\bar T(k)+\bar T(n-k)\Big)+\Theta(n). \end{equation}

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

\begin{equation} \frac{1}{n}\big(\bar T(1)+\bar T(n-1)\big)=\frac{1}{n}\big(\Theta(1)+O(n^2)\big)=O(n), \end{equation}

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

\begin{equation}\label{eqtrbis} \bar T(n)=\frac{2}{n}\sum_{k=1}^{n-1}\bar T(k)+\Theta(n). \end{equation}

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 montrer par récurrence que \(\bar T(n)\leq an\log n +b\) pour deux constantes \(a\) et \(b\) à déterminer. C'est évidemment vrai pour \(n=1\), et en appliquant l'hypothèse de récurrence, on a

\begin{align*} \bar T(n)&\leq\frac{2}{n}\sum_{k=1}^{n-1}(ak\log k +b) +\Theta(n)\\ &=\frac{2a}{n}\sum_{k=1}^{n-1}(k\log k)+\frac{2b}{n}(n-1)+\Theta(n)\\ &\leq\frac{2a}{n}\sum_{k=1}^{n-1}(k\log k)+2b+\Theta(n). \end{align*}

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

\begin{equation} \sum_{k=1}^{n-1}(k\,\log k)\leq\int_1^nx\,\log x\,\text{d}x, \end{equation}

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

\begin{equation*} \sum_{k=1}^{n-1}(k\log k)\leq\frac{1}{2}\left[x^2(\log x-\frac{1}{2})\right]_1^n=\frac{n^2}{2}(\log n -\frac{1}{2})+\frac{1}{4}. \end{equation*}

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

\begin{align*} \bar T(n)&\leq an(\log n -\frac{1}{2})+\frac{a}{2n}+2b+\Theta(n)\\ &=an\log n+b-\frac{an}{2}+\frac{a}{2n}+b+\Theta(n)\\ &\leq (an\log n+b)+\Theta(n)+a+b-\frac{an}{2}. \end{align*}

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.

La complexité moyenne du tri rapide est en \(O(n\log n)\).

Travaux pratiques

Implantez l'algorithme du tri rapide et vérifiez expérimentalement que sa complexité moyenne est conforme au calcul. Reprenez cette suggestion pour engendrer une permutation aléatoire. Étudiez l'influence du désordre du tableau sur le temps de calcul. Pour cela, partez de la permutation identité et appliquez un nombre croissant de transpositions des termes choisis au hasard. Tracez vos courbes avec Gnuplot.
Modifiez l'algorithme du tri rapide de manière à ce que l