1. Conçu par C. A. R. HOARE, Quicksort, Computer Journal, 1962.
On considère un ensemble de n valeurs à trier V1, V2, V3 ... Vn. On partionne cet ensemble en deux parties, comportant sensiblement le même nombre d'élément ; pour cela, on fait en sorte que l'une des parties contienne les éléments de valeur inférieure à Vm "médiane"2, l'autre les éléments de valeur supérieure à Vm. Si l'ensemble d'origine est "bien" désordonné (c.-à-d. les éléments répartis de façon parfaitement aléatoire) il y a au départ la moitié des éléments qui ne sont pas dans la partie où ils doivent se trouver après la partition ; on peut déplacer ces éléments vers la bonne partie par n/4 échanges d'éléments mal placés. Ensuite on applique récursivement le même traitement à chacune des deux parties séparément : on aura encore 2((n/2)/4) échanges ; à chaque fois la relation d'ordre entre les éléments appartenant aux nouvelles parties est établie. On réitère tant que les parties ont plus d'un élément (c.-à-d. ≈ log2(n) fois). A la fin, l'ensemble a été partitionné en n parties d'un élément ; la relation d'ordre entre les parties est vérifiée, donc l'ensemble est ordonné ; ces opérations ont eu une complexité en Θ(n log(n)) comparaisons et échanges.
2. Une valeur m est dite médiane pour un ensemble, si cet ensemble comporte autant d'éléments de valeurs inférieures à m que d'éléments de valeurs supérieures à m.
Principe du tri par partition
On peut jeter les bases d'une procédure QS : les n éléments à trier sont rangés dans un tableau t[ng..nd] (avec n ≡ nd - ng + 1) ; on demande la procédure partitionner de séparer t en 2 sous-tableaux et de rendre k_front, indice de la drontière de ceux-ci.
Procédure QS (t, ng, nd) partitionner (t, ng, nd, k_front) QS (t, ng, k_front...) QS (t, k_front..., nd)
Il nous faut préciser nos choix3 et développer la procédure partitionner.
3. Dans la suite, les points de suspension dans la notation k_front... serviront à rappeler que la définition de l'élément frontière n'est pas achevée.
4. Il faut signaler qu'il existe de très nombreuses variantes de l'algorithme Quicksort.
Nous appelons "valeur pivot" V_piv la valeur - supposée - médiane qui ser à partitionner le tableau t (cette valeur pivot ne peut être que la valeur d'un élément du tableau). Soit k_piv son indice (nous discuterons plus loin du choix de cet élément).
la formulation de la condition de partition devient : t [ng..k_front...] < V_piv < t [k_front... ..nd]
Une fois de plus apparaît l'interrogation "< ou ?", le fait qu'on ne puisse écarter la possibilité que plusieurs élément de t soient égaux, au moins un signe
s'impose maix où?
Les considérations suivantes peuvent nous aider dans nos choix :
Spécifions la plus précisément :
procédure partitionner (t, bg, bd, k_front) /* suppose que t[bg..bd] n'est pas vide */ /* détermine "k_front" tel que t[bg..k_front-1]t(k_front)
t[k_front+1..bd] */
L'idée est très simple : on choisit k_piv donc V_piv t(k_piv) ; on explore t en partant des deux extrémités jusqu'à rencontrer deux éléments à échanger c.-à-d. tels que t[kg] > V_piv et t[kd] < V_piv avec kg < kd ; on échange ces éléments, puis on recommence jusqu'à épuisement.
Comme d'habitude, on suppose qu'on a déjà réalisé une partition partielle5 : t[bg..rg-1] V_piv
t[rd+1..bd] et qu'il reste un sous-tableau, non vide, t[rg..rd] à partitionner.
5. En cas de besoin, on peut toujours imaginer (à condition de ne pas y toucher!) qu'il existe deux éléments virtuels : t(bg-1) ≡ - et t(bd+1) ≡ -
Voici le principe de la recherche avant échange :
kgrg /* il reste t[rg..rd] non vide, c.-à-d. rg
rd */ kd
rd répéter /* exploration pour kg croissant */ tantque t(kg)
V_piv kg
kg + 1 fin_répéter répéter /* exploration pour kd décroissant */ tantque t(kd)
V_piv kd
kd - 1 fin_répéter
On doit alors échanger t(kg) et t(kd) puis réitérer après avoir mis à jour rg et rd : rg kg et rd
kd. Il faut en outre prévoir l'arrêt. (Remarque : On pourrait être tenté de mettre à jour t(kg) et t(kd) puis réitérer après avoir mis à jour rg et rd par rg
kg+1 et rd
kd-1 mais on n'aurait plus l'assurance que rg
rd.
Analyse des situations possibles (en italique : les conditions logiques vérifiées à chaque pas) :
répéter /* on suppose rgrd */ kg
rg kd
rd ici : bg
rg
kg
kd
rd
bd répéter /* exploration pour kg croissant */ si kg > kd sortir des 2 boucles imbriquées sortie 1 ici : bg
rg
kg
kd
rd
bd tantque t(kg)
V_piv si on sort : kd
kd et t(kg) > V_piv kd
kd + 1 sinon ici : kg
kd+1 et t(kg-1)
V_piv fin_répéter ici : bg
rg
kg
kd
rd
bd et k(kg) > V_piv répéter /* exploration pour kd décroissant */ si kd < kg sortir des 2 boucles imbriquées sortie 2 ici : bg
rg
kg
kd
rd
bd tantque t(kd)
V_piv si on sort : kg
kd et t(kd) < V_piv kd
kd - 1 sinon ici : kg-1
kd et t(kd+1)
V_piv fin_répéter ici : bg
rg
kg
kd
rd
bd et t(kg) > V_piv > t(kd), donc kg
kd échanger (t(kg), t(kd)) rg
kg rd
kd fin_répéter (conditions plus fortes que celles supposées au début de la boucle)
Il faut maintenant analyser la situation aux sorties pour choisir la valeur de k_front, c.-à-d. pour pouvoir mettre V_piv dans t(k_front) en échangeant t(k_piv) et t(k_front) :
Sortie 1 : bg rg
kd
rd
bd et kg > kd
kg ≡ kd + 1
Sortie 2 : bg rg
kg
rd
bd et kd < kg
kd ≡ kg - 1
On n'est pas sûr que kd bg mais on est sûr que kg
bg, et que t(kg)
V_piv, il faut déterminer k_front :
Remarquons qu'on peut unifier la déterminer de k_front, pour les deux sorties, en se rappelant que kg ≡ kd + 1 :
Et voici le texte (presque) complet de partitionner :
procédure partitionner (t : Entrée/Sortie bg, bd : Entrée k_front : Sortie) /* suppose que t[bg..bd] n'est pas videbg
rg
bd */ /* détermine "k_front" tel que */ /* t[bg..k_front-1]
t(k_front)
t[k_front+1..bd] */ k_piv
??? V_piv
t(k_piv) rg
bg rd
bd si rg < rd alors répéter /* boucle de recherche de 2 éléments à échanger */ kg
rg /* suppose rg
td et t[bg..rg]
V_piv
t[bd..rd] */ kd
rd répéter /* recherche de t(kg) > V_piv, exploration pour kg croissant */ tantque kd
kg /* "sortie 1" */ tantque t(kg)
V_piv kg
kg + 1 fin_répéter répéter /* recherche de t(kd) < V_piv, exploration pour kd décroissant */ tantque kg
kg /* "sortie 2" */ tantque t(kd)
V_piv kd
kd - 1 fin_répéter /* on a vu que ici : soit t(kg) > V_piv > t(kd), donc : kg
kd soit kg = kd+1, donc encore : kg
kd */ si kd > kg alors /* rétablir l'ordre puis continuer la boucle */ échanger (t(kg), t(kd)) rg
kg rd
kd /* continuer la boucle avec rg < rd */ sinon /* sortir de la boucle, on a kd < kg */ si k_piv
kd alors f_front
kd sinon f_front
kg fin_si échanger (t(k_piv), t(k_front)) cesser de répéter fin_si fin_répéter /* fin_boucle de recherche de 2 éléments à échanger */ sinon /* cas particulier : 1 élément */ k_front
bg fin_si fin_procédure partitionner
Si tout se passe très bien (c.-à-d. que, à chaque fois, V_piv est médiane du sous-tableau), nous avons montré une complexité en Θ(n log(n)). Mais si le choix de V_piv conduit, à chaque fois, à une valeur de k_front égale à bg ou bd il y aura bd-bg comparaisons, donc partitionner n'aura pu retirer qu'un seul élément du sous-tableau ; on voit aisément que, si ce comportement pathologique se reproduit, la complexité passe à Θ(n²). Une telle situation peut se produire assez facilement si le tableau initial est quasi-trié. La probabilité de cette situation croit aussi lorsque la taille du tableau diminue (probabilité qu'un élément pris parmi n soit le plus grand, ou le plus petit), cependant si la taille du tableau est faible, l'effet de la complexité en Θ(n²) cesse d'être important.
Nous avons vu que l'efficacité de la méthode est liée au fait que la valeur du pivot soit médiane des valeurs des éléments du tableau. Eliminons tout de suite la tentation de parcourir préalablement chaque sous-tableau pour en déterminer la médiane, ce procédé nous conduirait immédiatement à une compléxité en Θ(n²).
Pour tenter d'éviter un valeur pivot trop excentrique voici deux suggestions :
Une fois définie la procédure partitionner, l'écriture de QS est très grave :
procédure QS (t : tableau_à_trier : Entrée/Sortie; ng, nd : indices pour t : Entrée ) variable locale k_front : indice pour t si ng < nd alors partitionner (t, ng, nd, k_front) QS (t, ng, k_front - 1) QS (t, k_front + 1, nd) fin_si fin_procédure QS
Cette procédure est récursive, mais comme le second appel à QS est un appel terminal on peut aisément transformer ce deuxième appel récursif en itération.
D'autre part, pour limiter les coûts (nombre d'appels récursifs et profondeur de la pile de récursion) on voit aisément que, si les deux partitions sont de tailles inégales, il vaut mieux traiter d'abord la plus petite partition. Cette précaution permet de limiter dans tous les cas la hauteur de la pile de récursion à log2(n).
Enfin, pour obtenir la plus grande rapidité : dérécursifier complètement.
Le programme suivant, écrit en FORTRAN 66, implémente-t'il un tri par partition ?
SUBROUTINE TRIF(A,N,II,JJ) C BUT : LE SOUS-PROGRAMME TRIF PERMET DE RANGER DANS L'ORDRE CROISSANT C TOUT OU PARTIE D'UN TABLEAU DE NOMBRES. C APPEL : CALL TRIF(A,N,II,JJ) C ARGUMENTS : A : TABLEAU FLOTTANT CONTENANT LES NOMBRES A RANGER DANS L'ORDRE CROISSANT C N : ARGUMENT ENTIER, DIMENSION DU TABLEAU A C II : ARGUMENT ENTIER, INDICE INFERIEUR DE LA PARTIE DU TABLEAU A A RANGER C JJ : ARGUMENT ENTIER, INDICE SUPERIEUR DE LA PARTIE DU TABLEAU A A RANGER C APRES L'APPEL DE TRIF, LA PARTIE DU TABLEAU A DEFINIE PAR : A(I), II.LE.I.LE.JJ EST C RANGEE DANS L'ORDRE CROISSANT C REMARQUES PRATIQUES : LE SOUS-PROGRAMME TRIF UTILISE DEUX TABLEAUX IU ET IL DE DIMENSION C M=20, CE QUI PERMET DE TRAITER DES TABLEAUX DE DIMENSION N AVEC : N.LT.2**(M+1). C POUR FAIRE DE TRIF UN SOUS-PROGRAMME DE TRI DECROISSANT, IL SUFFIT DE REMPLACER LT, LE, C GE, GT RESPECTIVEMENT PAR GT, GE, LE, LT DANS LES INSTRUCTIONS 32, 37, 41, 49, 52, 75 C ET 79. C METHODE : TRIF UTILISE LA METHODE DE SELECTION DE PLACE . VOIR : COMM ACM - VOL 12 - NO 3 - C MARS 1969 - P185-187 - 'AN EFFICIENT ALGORITHM FOR SORTING WITH MINIMEL STORAGE' C PAR SINGLETON. DIMENSION A(N), IU(20), IL(20) M=1 I=II J=JJ 5 IF (I.GE.J) GO TO 70 10 K=I IJ=(J+I)/2 T=A(IJ) IF (A(I).LE.T) GO TO 2O A(IJ)=A(I) A(I)=T T=A(IJ) 20 L=J IF (A(J).GE.T) GO TO 40 A(IJ)=A(J) A(J)=T T=A(IJ) IF (A(I).LE.T) GO TO 40 A(IJ)=A(I) A(I)=T T=A(IJ) GO TO 40 30 A(L)=A(K) A(K)=TT 40 L=L-1 IF (A(L).GT.T) GO TO 40 TT=A(L) 50 K=K+1 IF (A(K).LT.T) GO TO 50 IF (K.LE.L) GO TO 30 IF ((L-I).LE.(J-K)) GO TO 60 IL(M)=I IU(M)=L I=K M=M+1 GO TO 80 60 IL(M)=K IU(M)=J J=L M=M+1 GO TO 80 70 M=M-1 IF (M.EQ.0) GO TO 110 I=IL(M) J=IU(M) 80 IF ((J-I).GE.11) GO TO 10 IF (I.EQ.II) GO TO 5 I=I-1 90 I=I+1 IF (I.EQ.J) GO TO 70 T=A(I+1) IF (A(I).LE.T) GO TO 90 K=I 100 A(K+1)=A(K) K=K-1 IF (T.LT.A(K)) GO TO 100 A(K+1)=T GO TO 90 110 RETURN END