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éfavorables 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é.

L'algorithme présenté ici est la version originelle dans laquelle le pivot est fixé à la première valeur. 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 après le partitionnement et qui rend inutile l'opération de fusionnement au retour des appels récursifs : les éléments de la sous-liste \(L[p\!:\!q]\) sont tous inférieurs à tous les éléments de la sous-liste droite \(L[q+1\!:\!r],\) i.e.

\begin{equation} \label{eq:proptr} \forall i\in\ab{p}{q}\ \ \forall j\in\ab{q+1}{r}\quad L[i] \leqslant L[j], \end{equation}

que l'on résume par

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

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 échan­geant des valeurs dans la liste pendant la phase de par­ti­tion­ne­ment, cette phase ne se limite donc pas à dé­ter­mi­ner la position \(q\) de la césure. L'algorithme 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. 

ALGORITHME Tri-Rapide(@L,p,r)
DONNEES
   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\) à la ligne #10 tient au fait qu'elle est suivie à la ligne #11 par un appel à l'algorithme Reculer qui la décrémente une première fois, la sentinelle droite part bien de la fin de la sous-liste considérée en \(r.\) 

ALGORITHME Reculer(L,x,@j)              ALGORITHME Avancer(L,x,@i)
DONNEES                                 DONNEES
   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 

ALGORITHME Partitionner(@L,p,r):entier
DONNEES
   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

Vous pouvez observer ci-dessous la trace de l'exécution de l'algorithme Partitionner pour une liste quelconque. 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 si \(i=j\).

\(L=[\)\(]\)

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 deux valeurs. Avant l'entrée dans la boucle principale #14, vérifions que la proposition suivante est vraie :

\begin{equation*} \label{assert} (i=p)\land(i\leqslant j\leqslant r)\land (L[p:i]\leqslant x\leqslant L[j+1:r]). \end{equation*}

En effet, avant la boucle #11, \(i:=p\) puis \(j\) décroit jusqu'à ce que l'on atteigne une valeur \(\leqslant 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

\begin{equation} (i=p)\land (i \lt j\leqslant r)\land (L[p:i]\leqslant x\leqslant L[j:r])\land (L[j]=x). \end{equation}

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 (lignes #09 de chacun des algorithmes Avancer et Reculer), on a toujours \(p\leqslant j\) et \(i\leqslant 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]\leqslant x\) et \(x\leqslant 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]\leqslant 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 peut se produire que quand \(L[j]\) égale la valeur du 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)\in \ab{p}{r}\quad i\leqslant j\ \then\ L[i]\leqslant L[j]. \end{equation*}

Considérons donc \(i\) et \(j\) deux entiers de l'intervalle \(\ab{p}{r}\) tels que \(i\leqslant 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é.

Montrez que le tri rapide n'est pas stable
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

\begin{equation} \label{eq:trirapgen} \color{#FFF}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 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

\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 \(\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 :

\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 et il nous faut classer les \(n!\) instances possibles en fonction du nombre d'opérations réalisées par l'algorithme de partitionnement pour les traiter.

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 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 \(\prob[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ée :

Soit \(L\) une liste de \(n\) éléments d'un ensemble totalement ordonné \(X\) et \(x\in X.\) On appelle rang de \(x\) dans \(L,\) le nombre de termes inférieurs ou égaux à \(x\) dans \(L\) : \begin{equation} \text{rang}_{\;L}(x):=\#\{i\in\ab{1}{n}\ \mid\ L[i]\leqslant x\}. \end{equation}

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\) 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. Le pivot \(x\) est désormais à sa position définitive dans la liste, l'indice \(j\) restera donc 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}_{\;L}(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

\[\forall i\in\ab{1}{n}\quad \prob[\text{rang}_{\;L}(x)=i]=\frac{1}{n}.\] Par conséquent la valeur \(q=1\) est obtenue pour \(\text{rang}_{\;L}(x)=1\) ou \(\text{rang}_{\;L}(x)=2\). La probabilité que la sous-liste gauche soit réduite au seul premier terme de la liste à l'issue du partitionnement est donc deux fois plus grande que les autres situations :

\begin{equation*} \prob[q=k]= \begin{cases} \frac{2}{n}&\text{si}\ k=1.\\ \frac{1}{n}&\text{si}\ 2\lt k\leqslant n. \end{cases} \end{equation*}

Nous pouvons maintenant intégrer tous ces calculs dans (\ref{eq:trirapgen}) (rappelée ci-dessous) pour obtenir \[ T(n) = T(q)+ T(n-q) + \Theta(n). \]

On a donc \begin{align} \overline{T}(n) &= \frac{2}{n}(\overline{T}(1)+\overline{T}(n-1))+\frac{1}{n}\sum_{q=2}^{n-1}\Big(\overline{T}(q)+\overline{T}(n-q)\Big) \\ \label{eqtr} &={\color{#FF8}\frac{1}{n}\big(\overline{T}(1)+\overline{T}(n-1)\big)}+\frac{1}{n}\sum_{q=1}^{n-1}\Big(\overline{T}(q)+\overline{T}(n-q)\Big)+{\color{#88F}\Theta(n)}. \end{align}

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

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

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

\begin{equation}\label{eqtrbis} \overline{T}(n)=\frac{2}{n}\sum_{q=1}^{n-1}\overline{T}(q)+\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 mon­trer par récurrence forte que \(\overline{T}(n)\leqslant an\log n +b\) pour deux constantes \(a\) et \(b\) à déterminer. Le prédicat \(P(n)\) est donc \(\overline{T}(n)\leqslant 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).\)
L'initialisation est évidente, et en appliquant l'hypothèse de récurrence forte, on a

\begin{align*} \overline{T}(n) &\leq\frac{2}{n}\sum_{q=1}^{n-1}(aq\log q +b) +\Theta(n)\\ &=\frac{2a}{n}\sum_{q=1}^{n-1}(q\log q)+\frac{2b}{n}(n-1)+\Theta(n)\\ &\leq\frac{2a}{n}\sum_{q=1}^{n-1}(q\log q)+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_{q=1}^{n-1}(q\,\log q)\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_{q=1}^{n-1}(q\log q)\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*} \overline{T}(n) &\leqslant 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)\\ &\leqslant (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}\leqslant 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

On se propose d'écrire le code du tri rapide en langage \(C\). Pour éviter de passer deux arguments, le tableau et sa taille, déclarez la structure TLISTE suivante pour représenter les listes d'une part, et une structure telem qui permettra de modifier facilement le type des objets contenus dans les tableaux : 

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

Écrivez une fonction uint Partitionner(tliste L, uint p, uint r) qui renvoie la valeur \(q\) assurant le bon partitionnement de la sous-liste \(L[p,q]\) avec la sous-liste \(L[q+1,r]\) dans la sous-liste \(L[p,r]\).
Écrivez une fonction void TriRapide(tliste L, uint p, uint r) qui trie une liste \(L\) avec l'algorithme du tri rapide. Vérifiez de manière empirique, en triant des permutations aléatoires de différentes tailles (cf. tris empiriques) que la complexité moyenne de ce tri est conforme au cours.

Indication : Pour tester des permutations aléatoires générées avec l'algorithme de Fisher-Yates, écrivez un programme genperm.c qui renvoie sur la sortie standard \(n\) valeurs entières, où \(n\) est passé en argument de la ligne de commande. Vous pouvez éventuellement rajouter d'autres paramètres pour fixer la nature des valeurs renvoyées (positives, bornées, etc.) pour rendre votre générateur plus versatile.

Écrivez un algorithme tbool EstTrie(tliste L) qui renvoie vrai si la liste passée en paramètre est triée et faux sinon (typedef enum{FAUX=0,VRAI=1} tbool;). Modifiez l'algorithme du tri rapide en TriRapideTest de manière à ne pas faire d'appel récursif sur une sous-liste qui aurait été triée à l'issue du partitionnement.
Modifiez l'algorithme du tri rapide en appliquant une permutation aléatoire à la liste initiale avant de faire les appels récursifs. Comparer le comportement moyen de cette nouvelle version avec la version originale. Saisissez les éléments de la liste sur l'entrée standard, en convertissant les arguments dans le type telem fixé.
Comparez les complexités moyennes (en nombre de comparaisons) du tri fusion et du tri rapide en traçant les courbes de complexité avec Gnuplot.