TP-Cours ITC 10

Tri rapide ou quicksort

I. Généralités, exemples

Comme dans le TP-Cours n°09 (tri par insertion), on s’intéressera ici au tri par ordre croissant usuel d’une liste/d’un tableau d’entiers, c’est-à-dire que la liste $L$ de longueur $n \in N^{*}$ sera considérée comme triée si pour tout $(i, j) \in [[0; n - 1]]^{2}$ , $i ⩽ j ⟹ L [i] ⩽ L [j]$
Cette propriété revient également à dire que pour tout $i \in [[0; n - 2]], L [i] ⩽ L [i + 1]$ .

Qu'est-ce que le tri rapide ? Quelle différence avec le tri par insertion ?

Une première réponse dans cette vidéo "aux gobelets"

Le tri rapide ou QuickSort en anglais est un algorithme de tri inventé par C.A.R. Hoare en 1961 et fondé sur le paradigme «diviser pour régner» que nous avons déjà étudié à l’occasion du TP-Cours n°08 sur la dichotomie.

L’algorithme du tri rapide a un temps d’exécution/une complexité dans le pire des cas de $O (n^{2})$ lorsqu’il s’applique à un tableau de $n \in N^{*}$ nombres. En dépit de ce temps d’exécution lent, dans le pire des cas, le tri rapide est souvent le meilleur choix en pratique, grâce à son efficacité remarquable en moyenne du type $O (n \ln n)$ .

Le tri rapide fonctionne en sélectionnant un élément pivot qui est ensuite utilisé pour trier les éléments restants du tableau. Tout élément ayant une valeur inférieure ou égale au pivot est déplacé vers la « gauche » du pivot dans le tableau, tandis que tout élément supérieur au pivot est déplacé vers la « droite ». L’élément pivot sera donc «à sa place» dans le tableau de départ.

Il existe de nombreuses versions différentes de cet algorithme QuickSort qui sélectionnent le pivot de différentes manière, avec plus ou moins de raffinement, afin de minimiser le nombre d’opérations (comparaisons, échanges d’éléments ) effectuées sur un tableau pour réaliser ce partitionnement. Dans la suite, nous choisirons comme pivot le dernier élément du tableau en entrée et de chaque sous-tableau à trier.

Une fois le tableau parent partitionné, on trie ensuite les sous-tableaux en utilisant la même méthode, en divisant continuellement le tableau jusqu’à ce que tous les éléments aient été triés. L’algorithme du tri rapide est donc naturellement récursif.

La condition d’arrêt des appels récursifs de QuickSort est très simple : si le tableau actuel a strictement moins de deux éléments (c’est-à-dire qu’il a un seul élément ou qu’il est vide), on a trié ce tableau et aucune tâche n’est réalisée par l’algorithme. Chaque sous-tableau est partitionné à plusieurs reprises, divisé de manière récursive jusqu’à ce que la condition d’arrêt soit atteinte, moment auquel les divers sous-tableaux réunis forment un tableau-parent trié. Le tri rapide est un algorithme de tri «en place» puisque nous allons voir qu’aucune nouvelle structure de données n’est créée au cours de son exécution et que toutes les opérations sont directement sur le tableau en entrée.

Voici les trois étapes du processus « diviser pour régner »
employé pour trier un sous-tableau typique

L[a:b+1]=[L[a],...L[b]]

L[a:b+1]=[L[a],...L[b]]

Diviser : le tableau
L[a:b+1]
L[a:b+1] est partitionné en deux sous-tableau et un pivot soit L[a:iPivot],L[iPivot],L[iPivot+1:b+1]
L’indice
iPivot
iPivot est calculé pendant la procédure de partitionnement. À l’issue de cette étape, ne sont pas triés.
Régner : les deux sous-tableaux sont triés par des appels récursifs de la procédure principale du tri rapide.
Combiner : comme les sous-tableaux sont triés «en place», aucun travail n’est nécessaire pour les recombiner. Le tableau
L[a:b+1]
L[a:b+1] en entier est maintenant trié.

Le processus clé dans le tri rapide est la fonction

partition(L:list, a:int, b:int)→pos:int

partition(L:list, a:int, b:int)→pos:int qui réalise le partitionnement de la liste/du tableau

L[a:b+1]

L[a:b+1] et positionne le pivot

L[b]

L[b] «à sa place» dans

L . Ce travail doit être réalisé en temps linéaire.

Il existe deux algorithmes populaires pour partitionner le tableau en jeu. Les schémas de partition Lamuto et Hoare trient tous les deux avec succès le tableau donné, bien que le schéma Hoare soit généralement considéré comme plus efficace. Le schéma de Lamuto exécute en moyenne 3 fois plus de swaps que le schéma de Hoare. Le schéma de Hoare l’emporte lorsque le tableau contient de nombreux éléments répétés, car celui de Lamuto échangerait à plusieurs reprises des éléments répétés inutilement.

Ici, nous utiliserons le schéma de Lamuto, d’abord plus facile. Il utilise deux compteurs entiers $i P i v o t$ initialisé à $a$ et $i$ variant entre a et $b - 1$ . Chaque fois que $L [i]$ est inférieur ou égal au pivot $L [b]$ , on échange $L [i]$ et $L [i P ï v o t]$ puis $i P i v o t$ est incrémenté de 1 de sorte qu’en fin de boucle sur $i$ , les éléments plus petits que $L [b]$ se retrouvent tous dans les positions $a, \dots, i P i v o t - 1$ et ceux qui sont strictement plus grand que $L [b]$ se retrouvent tous dans les positions $i P i v o t, \dots, b - 1$ .

Il ne restera plus, dès lors, qu’à échanger $L [b]$ et $L [i P i v o t]$ pour mettre le pivot «à sa place».

II. Algorithme et implémentation en Python

Question 1

Complétez le schéma suivant en appliquant l’algorithme de tri rapide tel que décrit dans l’exemple précédent.

Question 2

la fonction

partition(L:list, a:int, b:int)→ pos:int

partition(L:list, a:int, b:int)→ pos:int qui réalise le partitionnement de la liste/du tableau

L[a:b+1]

L[a:b+1] et positionne le pivot

L[b]

L[b] «à sa place» dans

L : le tout en temps linéaire.

Question 3

Écrire l’algorithme de la fonction

triRapide(L:list, a:int, b:int)→ None

triRapide(L:list, a:int, b:int)→ None qui réalise le tri rapide de la liste

L[a:b+1]

L[a:b+1] puis implémenter cet algorithme en Python.