> Cours > Informatique> Algorithmique et Analyse > Tri par partition (Quicksort)

8. Tri par partition (Quicksort)

8.1. Idée de base¹

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"², 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. ≈ log₂(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.

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 choix³ et développer la procédure partitionner.

8.2. Choix⁴

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 :

• il est souhaitable que le nombre d'échanges soit aussi faible que possible. Ce qui entraîne qu'il ne faut faire d'échange que si on ne peut pas faire autrement (l'intérêt de retarder le plus possible les échanges est que plus l'échange d'un élément donné est tardif, plus le domaine où arrive cet élément est étroit, donc plus le nombre d'échanges ultérieurs possibles pour cet élément est limité) ; la condition t[ng..k_front...] V_piv t[k_front... ..nd] répond bien à cette préoccupation ; en particulier, elle laisse en place les éléments de valeur égale à P_piv (ce qui présente l'avantage marginal de ne pas avoir à placer, préalablement à la partition, l'élément pivot dans une position particulière, début ou fin, du tableau),
• il est indispensable que la procédure partitionner divise effectivement le tableau t en, au moins, 2 parties, même dans les cas exceptionnels (par exemple, quand V_piv est la valeur du plus grand, ou du plus petit, élément du tableau). Ce qui est assuré si on convient que partitionner doit découper t en 3 parties t[ng..k_front-1] V_piv t[k_front+1..nd] avec t(k_front) = V_piv ; partitionner engendre donc toujours 2 parties au moins (sauf dans le cas trivial n=1),
• enfin, il est recherché que les tailles de t[1..k_front-1] et t[k_front+1..n] soient comparables ; ce point dépend en premier lieu du fait que la valeur P_piv est médiane des valeurs des éléments de t[1..n].

8.3. Procédure partitioner

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 partielle⁵ : t[bg..rg-1] V_piv t[rd+1..bd] et qu'il reste un sous-tableau, non vide, t[rg..rd] à partitionner.

Voici le principe de la recherche avant échange :

kg  rg        /* 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 rg  rd */
    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

• on n'est pas sûr que kg bd mais on est sûr que kd bd, (on ne peut raisonner que sur kd)
• on est aussi sûr que t(kd) V_piv, (car, pour sortir ici, il faut avoir parcouru au moins une fois la boucle interne)
• il reste à déterminer k_front
  • si k_piv kd k_piv ∈ [bg..bd], on peut donc échanger t(kd) et t(k_piv) et choisir k_front kd
  • si (k_piv > kd) kd+1 bd, et on a t(kd+1) V_piv, on peut donc échanger t(kd+1) et t(k_piv) et choisir k_front kg

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 :

• si k_piv kd k_piv ≡ [bg..bd], on peut donc échanger t-kg) et t(k_piv) et choisir k_front kg
• sinon (k_piv > kd) kg-1 bg, et on a t(kg-1) V_piv, on peut donc échanger t(kg-1) et t(k_piv) et choisir k_front kd

Remarquons qu'on peut unifier la déterminer de k_front, pour les deux sorties, en se rappelant que kg ≡ kd + 1 :

• k_piv kd ≡ k_piv < kg k_front kd ≡ kg-1
• k_piv kd ≡ k_piv < kg k_front 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 vide          bg  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

8.4. Complexité

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.

8.5. Choix du pivot

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 :

• tirage aléatoire de l'indice du pivot (entre bg et bd), mais l'appel à un générateur de nombres pseudo-aléatoires risque de ralentir le programme ;
• choisir la valeur médiane des 3 : t(bg), t(bd) et t((bg+bd)/2) ce qui est en général efficace pour surmonter le cas des tableaux quasi-triés.

8.6. Procédure QS

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 à log₂(n).

Enfin, pour obtenir la plus grande rapidité : dérécursifier complètement.

8.7. Exercice

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