438
A Rappels algorithmiques
Mettre à sa place définitive la clé X choisie comme pivot, de telle sorte que les clés
inférieures ou égales à X se retrouvent à sa gauche, et que celles strictement supérieures à
X se retrouvent à sa droite ; puis trier récursivement les deux sous-listes ainsi obtenues.
Dans tout ce qui suit, le nombre n de clés à trier est constant. Supposons que
nous ayons à trier un sous-tableau T[gauche . . droite] dans un tableau T[1 . . n].
un choix classique 3 est de prendre T[gauche] comme pivot ; c’est celui que nous
ferons dans la suite de cette section. La procédure de placement doit trouver la place
k du pivot, bien sûr sans trier le tableau !
Fonction triRapide(tableau T, entier gauche, entier droite)
// Précondition : Pour tout j , 1 ≤ j ≤ n, T[j ] < T[n + 1].
// Postcondition : Retourne le tableau T, trié en ordre croissant.
// Utilise : partition, triRapide
// Variable locale : entier k
si gauche < droite alors
k, T = partition(T, gauche, droite)
T = triRapide(T, gauche, k - 1)
T = triRapide(T, k + 1, droite)
retourner T
Dans la fonction triRapide ci-dessus (comme dans la fonction partition
donnée plus loin), nous avons un tableau de taille, non pas n, mais n + 1. Cela
vient de l’ajout d’une dernière case, d’indice n + 1, qui contient une clé strictement
plus grande que toutes les autres clés du tableau. Son utilité est la suivante : lors
de la recherche de la place du pivot, il faut prévoir les cas où ce pivot est, soit plus
petit que tous les éléments déjà rencontrés, soit plus grand. Pour ne pas avoir à tester
systématiquement que les indices des cases restent bien dans les bornes adéquates, et
éviter les accès à d’autres cases que celles concernées par la procédure de partition,
voire les accès à des cases non existantes, il faut prévoir des sentinelles, à gauche
et à droite du tableau. La sentinelle gauche sera inférieure ou égale au pivot : elle
doit assurer l’arrêt de la boucle tant que T[haut] > T[gauche] de la fonction
partitionner. Si le pivot est choisi égal à T[gauche], il joue naturellement le
rôle de cette sentinelle gauche. Quant à la sentinelle droite, son rôle est d’assurer
l’arrêt de la boucle tant que T[bas] ≤ T[gauche] de la même fonction. Elle
est la plupart du temps présente lors des appels récursifs : c’est un ancien pivot
! Le seul cas susceptible de poser problème est celui où droite = n, i.e., où
nous travaillons sur la partie droite du tableau. 4 Pour le traiter, nous utilisons une
sentinelle en T[n+1], strictement plus grande que tous les éléments susceptibles
d’être présents dans le tableau. Dans la fonction partitionner ci-dessous, le
3 Il y en a d’autres, notamment prendre la médiane de plusieurs éléments.
4 En fait, en cas d’égalité des clés avec un ancien pivot, nous pouvons être amenés, dans le cas le
plus défavorable (lorsque toutes les clés à droite du tableau sont égales à cet ancien pivot) à aller
jusqu’à la dernière case du tableau ; mais la sentinelle évitera bien, dans ce cas aussi, de sortir du
tableau.
A Rappels algorithmiques
Mettre à sa place définitive la clé X choisie comme pivot, de telle sorte que les clés
inférieures ou égales à X se retrouvent à sa gauche, et que celles strictement supérieures à
X se retrouvent à sa droite ; puis trier récursivement les deux sous-listes ainsi obtenues.
Dans tout ce qui suit, le nombre n de clés à trier est constant. Supposons que
nous ayons à trier un sous-tableau T[gauche . . droite] dans un tableau T[1 . . n].
un choix classique 3 est de prendre T[gauche] comme pivot ; c’est celui que nous
ferons dans la suite de cette section. La procédure de placement doit trouver la place
k du pivot, bien sûr sans trier le tableau !
Fonction triRapide(tableau T, entier gauche, entier droite)
// Précondition : Pour tout j , 1 ≤ j ≤ n, T[j ] < T[n + 1].
// Postcondition : Retourne le tableau T, trié en ordre croissant.
// Utilise : partition, triRapide
// Variable locale : entier k
si gauche < droite alors
k, T = partition(T, gauche, droite)
T = triRapide(T, gauche, k - 1)
T = triRapide(T, k + 1, droite)
retourner T
Dans la fonction triRapide ci-dessus (comme dans la fonction partition
donnée plus loin), nous avons un tableau de taille, non pas n, mais n + 1. Cela
vient de l’ajout d’une dernière case, d’indice n + 1, qui contient une clé strictement
plus grande que toutes les autres clés du tableau. Son utilité est la suivante : lors
de la recherche de la place du pivot, il faut prévoir les cas où ce pivot est, soit plus
petit que tous les éléments déjà rencontrés, soit plus grand. Pour ne pas avoir à tester
systématiquement que les indices des cases restent bien dans les bornes adéquates, et
éviter les accès à d’autres cases que celles concernées par la procédure de partition,
voire les accès à des cases non existantes, il faut prévoir des sentinelles, à gauche
et à droite du tableau. La sentinelle gauche sera inférieure ou égale au pivot : elle
doit assurer l’arrêt de la boucle tant que T[haut] > T[gauche] de la fonction
partitionner. Si le pivot est choisi égal à T[gauche], il joue naturellement le
rôle de cette sentinelle gauche. Quant à la sentinelle droite, son rôle est d’assurer
l’arrêt de la boucle tant que T[bas] ≤ T[gauche] de la même fonction. Elle
est la plupart du temps présente lors des appels récursifs : c’est un ancien pivot
! Le seul cas susceptible de poser problème est celui où droite = n, i.e., où
nous travaillons sur la partie droite du tableau. 4 Pour le traiter, nous utilisons une
sentinelle en T[n+1], strictement plus grande que tous les éléments susceptibles
d’être présents dans le tableau. Dans la fonction partitionner ci-dessous, le
3 Il y en a d’autres, notamment prendre la médiane de plusieurs éléments.
4 En fait, en cas d’égalité des clés avec un ancien pivot, nous pouvons être amenés, dans le cas le
plus défavorable (lorsque toutes les clés à droite du tableau sont égales à cet ancien pivot) à aller
jusqu’à la dernière case du tableau ; mais la sentinelle évitera bien, dans ce cas aussi, de sortir du
tableau.