Kha-tastrophe.net

Le site kha-tastrophique de Kha

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

8. Tri par partition (Quicksort)

8.1. Idée de base1

1. Conçu par C. A. R. HOARE, Quicksort, Computer Journal, 1962.

fermer cette précision

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.

fermer cette précision

Principe du tri par partition

Schéma illustrant le principe du tri par partition

On sépare les n éléments en ≈ n/2 de valeurs inférieures à Vm et ≈ n/2 de valeurs supérieures à Vm si les éléments étaient initialement répartis de manière parfaitement aléatoire, il y a environ la moitié des éléments qui ne sont pas du bon côté, d'où n/4 échanges pour réaliser cette partition. Ensuite on réitère sur les éléments de chaque moitié...

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.

fermer cette précision

8.2. Choix4

4. Il faut signaler qu'il existe de très nombreuses variantes de l'algorithme Quicksort.

fermer cette précision

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 Symbole : inférieur et égal?", le fait qu'on ne puisse écarter la possibilité que plusieurs élément de t soient égaux, au moins un signe Symbole : inférieur et égal 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...] Symbole : inférieur et égal V_piv Symbole : inférieur et égal 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] Symbole : inférieur et égal V_piv Symbole : inférieur et égal 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] Symbole : inférieur et égal t(k_front) Symbole : inférieur et égal t[k_front+1..bd] */

L'idée est très simple : on choisit k_piv donc V_piv Symbole : affectation 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] Symbole : inférieur et égal V_piv Symbole : inférieur et égal 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) ≡ -Symbole : infini et t(bd+1) ≡ -Symbole : infini

fermer cette précision

Voici le principe de la recherche avant échange :

kg Symbole : affectation rg        /* il reste t[rg..rd] non vide, c.-à-d. rg Symbole : inférieur et égal rd */
kd Symbole : affectation rd
répéter       /* exploration pour kg croissant */
    tantque t(kg) Symbole : inférieur et égal V_piv
    kg Symbole : affectation kg + 1
fin_répéter
répéter       /* exploration pour kd décroissant */
    tantque t(kd) Symbole : supérieur et égal V_piv
    kd Symbole : affectation 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 Symbole : affectation kg et rd Symbole : affectation 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 Symbole : affectation kg+1 et rd Symbole : affectation kd-1 mais on n'aurait plus l'assurance que rg Symbole : inférieur et égal rd.

Analyse des situations possibles (en italique : les conditions logiques vérifiées à chaque pas) :

répéter                                                              /* on suppose rg Symbole : inférieur et égal rd */
    kg Symbole : affectation rg
    kd Symbole : affectation rd                                                        ici : bg Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal bd
    répéter /* exploration pour kg croissant */
        si kg > kd sortir des 2 boucles imbriquées                   sortie 1
                                                                     ici : bg Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal bd
        tantque t(kg) Symbole : inférieur et égal V_piv                                        si on sort : kd Symbole : inférieur et égal kd et t(kg) > V_piv
        kd Symbole : affectation kd + 1                                                sinon ici : kg Symbole : inférieur et égal kd+1 et t(kg-1) Symbole : inférieur et égal V_piv
    fin_répéter                                                      ici : bg Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal 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 Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal bd
        tantque t(kd) Symbole : supérieur et égal V_piv                                        si on sort : kg Symbole : inférieur et égal kd et t(kd) < V_piv
        kd Symbole : affectation kd - 1                                                sinon ici : kg-1 Symbole : inférieur et égal kd et t(kd+1) Symbole : supérieur et égal V_piv
    fin_répéter                                                      ici : bg Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal bd et t(kg) > V_piv > t(kd), donc kg Symbole : différent kd
    échanger (t(kg), t(kd))
    rg Symbole : affectation kg
    rd Symbole : affectation 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 Symbole : inférieur et égal rg Symbole : inférieur et égal kd Symbole : inférieur et égal rd Symbole : inférieur et égal bd et kg > kd Symbole : flèche double kg ≡ kd + 1

  • on n'est pas sûr que kg Symbole : inférieur et égal bd mais on est sûr que kd Symbole : inférieur et égal bd, (on ne peut raisonner que sur kd)
  • on est aussi sûr que t(kd) Symbole : inférieur et égal 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 Symbole : inférieur et égal kd Symbole : flèche double k_piv ∈ [bg..bd], on peut donc échanger t(kd) et t(k_piv) et choisir k_front Symbole : affectation kd
    • si (k_piv > kd) Symbole : flèche double kd+1 Symbole : inférieur et égal bd, et on a t(kd+1) Symbole : supérieur et égal V_piv, on peut donc échanger t(kd+1) et t(k_piv) et choisir k_front Symbole : affectation kg

Sortie 2 : bg Symbole : inférieur et égal rg Symbole : inférieur et égal kg Symbole : inférieur et égal rd Symbole : inférieur et égal bd et kd < kg Symbole : flèche double kd ≡ kg - 1

On n'est pas sûr que kd Symbole : supérieur et égal bg mais on est sûr que kg Symbole : supérieur et égal bg, et que t(kg) Symbole : supérieur et égal V_piv, il faut déterminer k_front :

  • si k_piv Symbole : inférieur et égal kd Symbole : flèche double k_piv ≡ [bg..bd], on peut donc échanger t-kg) et t(k_piv) et choisir k_front Symbole : affectation kg
  • sinon (k_piv > kd) Symbole : flèche double kg-1 Symbole : supérieur et égal bg, et on a t(kg-1) Symbole : inférieur et égal V_piv, on peut donc échanger t(kg-1) et t(k_piv) et choisir k_front Symbole : affectation 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 Symbole : inférieur et égal kd ≡ k_piv < kg Symbole : flèche double k_front Symbole : affectation kd ≡ kg-1
  • k_piv Symbole : supérieur et égal kd ≡ k_piv < kg Symbole : flèche double k_front Symbole : affectation 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         Symbole : flèche double bg Symbole : inférieur et égal rg Symbole : inférieur et égal bd */
        /* détermine "k_front" tel que */
        /* t[bg..k_front-1] Symbole : inférieur et égal t(k_front) Symbole : inférieur et égal t[k_front+1..bd] */
    k_piv Symbole : affectation ???
    V_piv Symbole : affectation t(k_piv)
    rg Symbole : affectation bg
    rd Symbole : affectation bd
    si rg < rd alors
        répéter        /* boucle de recherche de 2 éléments à échanger */
            kg Symbole : affectation rg       /* suppose rg Symbole : inférieur et égal td et t[bg..rg] Symbole : inférieur et égal V_piv Symbole : inférieur et égal t[bd..rd] */
            kd Symbole : affectation rd
            répéter        /* recherche de t(kg) > V_piv, exploration pour kg croissant */
                tantque kd Symbole : inférieur et égal kg     /* "sortie 1" */
                tantque t(kg) Symbole : inférieur et égal V_piv
                kg Symbole : affectation kg + 1
            fin_répéter
            répéter       /* recherche de t(kd) < V_piv, exploration pour kd décroissant */
                tantque kg Symbole : supérieur et égal kg     /* "sortie 2" */
                tantque t(kd) Symbole : supérieur et égal V_piv
                kd Symbole : affectation kd - 1
            fin_répéter 
            /* on a vu que ici : soit t(kg) > V_piv > t(kd), donc : kg Symbole : différent kd
                                 soit kg = kd+1, donc encore : kg Symbole : différent kd */
            si kd > kg alors         /* rétablir l'ordre puis continuer la boucle */
                échanger (t(kg), t(kd))
                rg Symbole : affectation kg
                rd Symbole : affectation kd      /* continuer la boucle avec rg < rd */
            sinon       /* sortir de la boucle, on a kd < kg */
                si k_piv Symbole : inférieur et égal kd alors
                    f_front Symbole : affectation kd
                sinon
                    f_front Symbole : affectation 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 Symbole : affectation 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 à log2(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