Table des matières

Tri rapide - Quicksort

Tony Hoare

Créé en 1960 par Tony Hoare, alors étudiant en visite à Moscou. Dans le cadre d'une étude sur la traduction automatique, il fallait un algorithme pour trier les mots venant d'être traduits pour les faire correspondre à un dictionnaire russe-anglais existant.

Il s'agit là encore de trier les items d'un tableau.

Principe

Le tri rapide ressemble au tri par fusion puisqu'il trie récursivement des demi tableaux. En revanche, le tri rapide est effectué en place, dans le tableau d'origine. Il ne nécessite pas la création de nombreux petits tableaux à fusionner plus tard. La complexité spatiale du tri rapide est donc réduite.

Fonction partition

Principe

On a besoin d'une fonction annexe, la fonction partition. On fournit à cette fonction :

Cette fonction choisit le pivot et place les autres éléments de la zone à gauche ou à droite du pivot.

exemple

Considérons le tableau : [0, 1, 6, 3, 5, 8, 17, 2, 9, 25, 32] en précisant que notre zone commence à l'indice 2 et termine à l'indice 8 – éléments mis en gras.

initialisation du pivot

Nous choisissons ici de toujours placer le pivot en début de zone.

[0, 1, 6, 3, 5, 8, 17, 2, 9, 25, 32]

Considérons maintenant les autres éléments : 3, 5, 8, 17, 2, 9

On souhaite les parcourir et les placer, pas forcément dans l'ordre, mais au moins de façon que les éléments inférieurs au pivot soient à gauche et les éléments supérieur au pivot à droite.

Les éléments égaux au pivot peuvent rester où ils sont car peu importe qu'ils soient à gauche ou à droite du pivot.

initialisation des curseurs

On place alors deux curseurs. Un partant de la gauche, l'autre partant de la droite de la zone considérée

[0, 1, 6, 3, 5, 8, 17, 4, 9, 25, 32]

marche des curseurs

On fait avancer le curseur gauche jusqu'à ce qu'il rencontre un élément strictement supérieur au pivot. Le curseur droite avance vers la gauche jusqu'à rencontrer un élément strictement inférieur pivot.

[0, 1, 6, 3, 5, 8, 17, 4, 9, 25, 32]

Le curseur gauche est sur 8 et le curseur droite est sur 4. Les deux valeurs sont du mauvais côté. On les permute.

[0, 1, 6, 3, 5, 4, 17, 8, 9, 25, 32]

L'avance des curseurs reprend.

croisement des curseurs

Il arrive un moment où le curseur gauche passe à droite du curseur droite.

[0, 1, 6, 3, 5, 4, 17, 8, 9, 25, 32]

C'est le signe qu'il faut arrêter.

déplacement du pivot

Dernière action, on permute le pivot avec le curseur droite.

[0, 1, 4, 3, 5, 6, 17, 8, 9, 25, 32]

fin de la fonction

On renvoie la position du pivot, ici 5.

Pas besoin de renvoyer le tableau car toutes ces opérations sont effectuées directement sur le tableau d'origine.

Algorithme de la fonction partition

Pour alléger la rédaction, je noterai cg pour curseur gauche et cd pour curseur droit.

Quand on avance cg, c'est toujours vers la droite. Quand on avance cd, c'est toujours vers la gauche. 

FONCTION partition
ENTRÉES
    tableau: le tableau à trier
    indice_debut: indice de début de la zone considérée
    indice_fin: indice de la fin de la zone considérée
PRÉCONDITION : 0 <= indice_debut <= indice_fin < longueur tableau
DÉBUT
    pivot est la valeur du tableau à l'indice indice_debut
    cg positionné à indice_debut + 1
    cd positionné à indice_fin
    TANT QUE cg à gauche de cd ou au même endroit FAIRE
        avancer cg jusqu'à atteindre
        un élément > pivot ou dépasser indice_fin
        avancer cd jusqu'à atteindre
        un élément < pivot ou la position indice_debut
        SI cg strictement à gauche de cd ALORS
            permuter les contenus des deux curseurs
            avancer cg et cd dans leur sens respectifs
        FIN SI
    FIN TANT QUE
    permuter le contenu à indice_debut (pivot) avec le contenu de cd
    RENVOYER position de cd
FIN
POSTCONDITIONS:
    indice_debut <= cd <= indice_fin
    tous les items de indice_debut à cd sont <= a l'item en cd
    tous les items de cd à indice_fin sont >= a l'item en cd
  • La précondition qui suppose que le tableau n'est pas vide.
  • La réponse renvoie un indice situé entre les indices de début et de fin.

Vérifier la correction

Je vous rappelle que l'on dit qu'un algorithme est correct quand, à condition que l'on vérifie les préconditions,

  • il termine
  • les postconditions sont vérifiées

Ce genre de vérification est un peu théorique et difficile mais il faut en faire de temps en temps…

  1. Justifier que l'algorithme termine toujours
  2. Justifier qu'à la fin, la première postcondition est toujours satisfaite.
  3. Justifier qu'à la fin de la boucle TANT QUE, le curseur droit est situé sur une valeur ⇐ pivot.
  4. Justifier qu'à la fin, après permutation pivot / cg, les deux autres postconditions sont vérifiées.

Un mot sur la complexité – plus difficile, passez si trop difficile.

Vous constatez que l'essentiel de la fonction consiste à faire traverser le tableau par les curseurs et que les curseurs ne font qu'une traversée simple. pour k = indice_fin - indice_debut, le coût de calcul est donc de l'ordre de k. Je rappelle que si l'analyse détaillée disait qu'en vérité c'était par exemple 15k + 17, on dirait : c'est d'ordre k.

Implémentation du tri rapide

def tri_rapide(tableau):
    n = len(tableau)
    tri_rapide_recursif(tableau, 0, n-1)

def tri_rapide_recursif(tableau, indice_debut, indice_fin):
    if indice_debut < indice_fin:
        limite = partition(tableau, indice_debut, indice_fin)
        tri_rapide_recursif(tableau, indice_debut, limite-1)
        tri_rapide_recursif(tableau, limite+1, indice_fin)

Vous remarquez que la fonction de tri rapide requiert deux arguments indice_debutet indice_fin qui doivent commencer, pour l'appel initial, à 0 et len(tableau) - 1. On crée donc une fonction qui amorce la récurrence.

Un mot sur la complexité – plus difficile, passez si trop difficile.

Soit $f(n)$ le coût de calcul pour un tableau de taille $n$. La fonction tri_rapide_recursif exécute partition de coût d'ordre $n$, puis deux fois la fonction tri_rapide_recursif avec un tableau de taille $\frac{n}{2}$ si on a de la chance – pivot bien choisi. Donc $f(n) = n + 2\times f\left(\frac{n}{2}\right)$ et $f(1) = 1$ – encore une fois ce sont les ordres de grandeur qui nous intéressent.

Ce genre d'évolution est typique d'un algorithme en $n\cdot \log_2(n)$

Vous remarquez que j'ai écrit “Si on a de la chance”. Tout repose sur le choix du pivot. Si on choisit, comme on l'a fait, le pivot systématiquement au début, on peut ne pas avoir de chance : si le pivot est la plus grandes des valeurs ou la plus petite ce qui fait que le partitionnement ne coupe pas bien en 2.

Pour éviter ce problème on pourrait complexifier un peu l'algorithme pour faire que le pivot soit toujours la valeur médiane de la zone a partitionner. Il existe des algorithme de calcul de médiane d'ordre linéaire (en $n$) ce qui n'augmente alors pas la complexité de l'algorithme.

À faire : dans un fichier `tri_rapide.py`, complétez l'implémentation précédente en y ajoutant l'implémentation de la fonction partition.