Table des matières
Tri rapide - Quicksort
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
- On choisit un item pivot au hasard. Par exemple, le premier item du tableau. Si on a de la chance, le pivot à une valeur à peu près médiane.
- On parcours le tableau de façon à placer à gauche du pivot tous les items inférieurs au pivot, et à droite tous les éléments supérieurs.
- On répète la fonction de tri sur les items à gauche du pivot et sur les items à droite du pivot.
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 :
- le tableau en cours de tri
- la position de début de la zone considérée
- la position de fin de la zone considérée
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…
- Justifier que l'algorithme termine toujours
- Justifier qu'à la fin, la première postcondition est toujours satisfaite.
- Justifier qu'à la fin de la boucle TANT QUE, le curseur droit est situé sur une valeur
⇐ pivot. - 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.