Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
Warning: Undefined array key 2 in /home/goupillf/wiki.goupill.fr/lib/plugins/codeprettify/syntax/code.php on line 214
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_debut
et 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
.