III.
Un algorithme de tri rapide : Quick Sort
La méthode consiste à mettre à sa place définitive l’un des éléments du tableau, appelé le pivot. Le
tableau est ensuite réorganisé autour de ce pivot, en mettant les éléments inférieurs au pivot à sa
gauche et les éléments supérieurs ou égaux au pivot à sa droite (sans les trier entre eux). On dit que
le tableau est partitionné autour du pivot.
A. Définition récursive
Décomposition du problème :
Trier un tableau revient à
- choisir un pivot et partitionner le tableau autour de ce pivot,
- trier le sous-tableau à gauche du pivot (pivot exclu),
- trier le sous-tableau à droite du pivot (pivot exclu).
Cas de base :
Lorsque le tableau est vide ou ne contient qu’un élément il n’y a rien à faire.
Comme le pivot n’appartient ni au sous-tableau gauche ni au sous-tableau droit, ces deux sous-
tableaux sont nécessairement strictement plus petits que le tableau initial.
B. La fonction de tri rapide
// Trie le tableau T[g…d] par ordre croissant
void quickSort(vector<int> &T, int g, int d)
{
if (g < d) // T[g…d] contient plus de 1 élément
{
int m = partition(T,g,d); // partitionne T[g…d] autour d’un
// pivot et renvoie la position de
// ce pivot
quickSort(T,g,m-1); // trie le sous-tableau gauche
quickSort(T,m+1,d); // trie le sous-tableau droit
}
}
C. Le choix du pivot
L’idéal serait que le pivot soit placé à peu près au milieu du tableau T[g…d] de telle sorte que la
fonction soit relancée sur deux sous-tableaux de tailles approximativement égales. Si le pivot vérifie
cette propriété, il est appelé l’élément médian du tableau : il y a autant d’éléments dans le tableau
qui sont plus petits que lui, que d’éléments qui sont plus grands (à un près). Il existe des algorithmes
Dominique Schmitt L3 Informatique et Mathématiques 7
qui permettent de rechercher l’élément médian d’un tableau en temps linéaire, mais ces algorithmes
ne sont pas faciles à mettre en œuvre et ne sont pas très efficaces en pratique. Il est préférable de
prendre un élément quelconque du tableau comme pivot. On peut en effet espérer, qu’en général,
cet élément va devoir être placé « à peu près au milieu » du tableau.
Pour notre implémentation, nous choisirons l’élément T[g] comme pivot.
D. La méthode de partition
On laisse d’abord le pivot à sa place initiale, c’est-à-dire en g. On place derrière lui tous les éléments
inférieurs au pivot et ensuite tous les éléments supérieurs ou égaux au pivot. Pour cela, on utilise
deux indices m et i qui sont tels que, à chaque instant de l’algorithme, le sous-tableau T[g+1...m]
contient les éléments déjà traités qui sont inférieurs au pivot, le sous-tableau T[m+1...i-1] contient
les éléments déjà traités qui sont supérieurs ou égaux au pivot, et le sous-tableau T[i...d] contient les
éléments non encore traités.
Le prochain élément à traiter est donc l’élément T[i]. Traiter l’élément T[i] revient à le comparer au
pivot. S’il est supérieur ou égal au pivot, il faut l’ajouter au sous-tableau T[m+1...i-1]. On peut
simplement laisser T[i] à sa place et augmenter i de 1. Si T[i] est inférieur au pivot, il faut l’ajouter au
sous-tableau T[g+1...m]. Pour cela, il suffit d’échanger T[i] avec l’élément en m+1 et d’augmenter m
et i de 1.
Au début de l’algorithme, il faut initialiser i à 1 puisqu’aucun élément n’a encore été traité : le sous-
tableau T[i...d] est ainsi le tableau complet, hors pivot. Pour la même raison, il faut initialiser m à g :
les sous-tableaux T[g+1...m] et T[m+1...i-1] sont encore vides.
Á la fin de l’algorithme, il suffit d’échanger T[g] et T[m] pour que le pivot soit à sa place.
// Réorganise le tableau T[g…d] autour du pivot T[g] et renvoie la
// position finale du pivot
int partition(vector<int> &T, int g, int d)
{
int m = g;
for (int i=g+1; i<=d; i++)
{
if (T[i] < T[g])
{ // échange de T[i] et T[m+1]
m++;
swap(T[i],T[m]);
}
}
swap(T[g],T[m]); // placement du pivot en T[m]
return m;
}
Dominique Schmitt L3 Informatique et Mathématiques 8
Remarques :
1) Les accolades de la boucle for (en rouge) ne sont pas nécessaires car elles n’encadrent qu’un test if
qui forme déjà un bloc. Cependant, certaines règles de programmation recommandent de toujours
mettre les accolades pour que le code soit plus facilement modifiable par la suite.
2) Les instructions
m++;
swap(T[i],T[m]);
peuvent être remplacées par
swap(T[i],T[++m]);
En effet, en plus d’incrémenter la variable m de 1, l’instruction ++m a une valeur : c’est la valeur de m
après qu’il a été incrémenté de 1. En revanche, on ne peut pas écrire
swap(T[i],T[m++]);
car la valeur de m++ est la valeur de m avant qu’il ait été incrémenté de 1.
E. Complexité
1. Cas général
La complexité de la fonction quickSort est déterminée par les instructions qui sont effectuées dans la
fonction partition. Comme cette fonction contient une boucle et que le test T[i] < T[m] est
effectué à chaque passage dans la boucle, on peut mesurer la complexité de quickSort en comptant
le nombre total de fois que ce test de comparaisons entre éléments est effectué.
Soit donc Nb(n) le nombre total de comparaisons entre les éléments du tableau qui sont effectuées
par la fonction quickSort pour trier un tableau de n éléments. La fonction partition effectue
exactement n-1 comparaisons. Le nombre de comparaisons nécessaires pour trier les sous-tableaux
T[g...m-1] et T[m+1...d] dépend de la taille de ces sous-tableaux, c’est à dire de la position à laquelle
doit être placé le pivot. Le sous-tableau gauche peut contenir un nombre d’éléments q qui varie
entre 0 et n-1. Le sous-tableau droit contient alors n-q-1 éléments. D’où la relation de récurrence
dans le cas général :
Nb(n) = n − 1 + Nb(q) + Nb(n − q − 1) avec 0 ≤ q ≤ n − 1 si n > 1
{
Nb(n) = 0 si n ≤ 1
2. Meilleur cas
Comme nous l’avons déjà remarqué dans la section C, pour que la fonction quickSort soit la plus
efficace possible, il faudrait qu’elle soit toujours relancée sur deux sous-tableaux de tailles
approximativement égales. Dans ce cas l’équation de récurrence deviendrait similaire à celle de la
fonction de tri par fusion et on trouverait également une complexité en O(n log n).
3. Pire cas
Le pire des cas se produit lorsque, à chaque appel récursif, les deux sous-tableaux sont aussi
déséquilibrés que possibles, c'est-à-dire lorsque l’un d’eux est vide et que l’autre contient tous les
éléments autres que le pivot. Dans ce cas, le pivot est à chaque fois soit le plus petit soit le plus grand
Dominique Schmitt L3 Informatique et Mathématiques 9
élément du tableau. Cela se produit notamment lorsque le tableau est déjà trié au départ. L’équation
de récurrence devient alors :
Nb(n) = n − 1 + Nb(0) + Nb(n − 1) = n − 1 + Nb(n − 1) si n > 1
{
Nb(n) = 0 si n ≤ 1
La résolution de cette équation donne
Nb(n) = n-1 + Nb(n-1)
Nb(n-1) = n-2 + Nb(n-2)
Nb(n-2) = n-3 + Nb(n-3)
Nb(3) = 2 + Nb(2)
Nb(2) = 1 + Nb(1)
Nb(1) = 0
En sommant membre à membre on obtient Nb(n) = (n-1) + (n-2) + (n-3) + … + 2 + 1.
Il s’agit ici de la somme des termes d’une suite arithmétique de raison 1. On rappelle que cette
somme peut être trouvée facilement en l’écrivant dans les deux sens et en sommant terme à terme.
Nb(n) = (n-1) + (n-2) + (n-3) + … + 3 + 2 + 1
Nb(n) = 1 + 2 + 3 + … + (n-3) + (n-2) + (n-1)
2Nb(n) = n + n + n + … + n + n + n
= (n-1)n
(n−1)n
D’où Nb(n) = 2
.
La complexité de quickSort est donc en O(n2) dans le pire des cas, ce qui est beaucoup moins bon que
le tri par fusion.
4. Cas moyen
En pratique, le pire des cas ne se produit que très rarement et on peut montrer que, en moyenne, la
complexité de quickSort est en O(n log n). La fonction quickSort et ses différentes variantes sont
même parmi les fonctions de tri les plus efficaces dans la pratique. La fonction sort de la
bibliothèque standard de C++ est une de ces variantes, appelée Introsort. C’est un hybride entre
quickSort et deux autres algorithmes de tri (le tri par insertion et le tri par tas). Cela permet à la
fonction sort d’être tout à la fois efficace en pratique et en O(n log n) dans le pire des cas. Pour
utiliser la fonction sort dans un programme C++, il faut inclure le fichier entête algorithm.
Dominique Schmitt L3 Informatique et Mathématiques 10
