3.3 Tri d’un ensemble de clés
79
Fig. 3.14 En haut, le tableau
T initial, avec le pivot x en
T [0]. En bas, le tableau T à la
fin de l’algorithme de
partition et placement du
pivot x : le pivot est à sa place
définitive T [k], et les deux
sous-tableaux T 1 et T 2 restent
à trier récursivement
Dans un tableau de clés, choisir une clé x comme pivot, trouver sa place définitive dans le
tableau en faisant appel à l’algorithme PARTITION, qui de plus réarrange ledit tableau de
telle sorte que les clés inférieures ou égales à x soient à sa gauche, et les clés supérieures à
sa droite, puis trier récursivement les deux sous-tableaux ainsi créés.
Lien tri rapide – arbre binaire de recherche
Revenons à la version classique du tri rapide. Ce tri agit sur un tableau, c’est-àdire sur une suite de clés : la représentation dans un tableau induit un ordre sur les
clés. Dans ce qui suit, nous allons identifier un tableau de n clés et une suite de la
même taille. Le processus de partitionnement d’un tableau de n clés, suivi d’appels
récursifs sur les sous-tableaux, ressemble beaucoup à la construction statique d’un
arbre binaire de recherche sur le même ensemble de clés.
Pour rendre explicite ce lien entre le tri rapide et les arbres binaires de recherche,
nous allons considérer non pas la version informatique usuelle de l’algorithme
PARTITION, qui est donnée en annexe A.6.1 et qui fait appel à une « sentinelle »,
i.e., à une clé supplémentaire, placée en fin de tableau et servant à éviter de
vérifier systématiquement que l’indice de la case testée est bien dans les bornes du
tableau, mais une version sans sentinelle et où chaque clé du tableau est comparée
exactement une fois au pivot. 12
Regardons alors les comparaisons de clés faites pour placer le pivot, que nous
supposons être la première clé d’un tableau de taille n : ces comparaisons sont entre
le pivot et les autres clés, et il y en a exactement n − 1. De façon parallèle, si nous
construisons un arbre binaire de recherche en insérant les clés dans l’ordre où elles
se présentent dans le tableau, la même clé x qui sert de pivot va se retrouver à la
racine de l’arbre et toutes les autres clés seront comparées exactement une fois à x.
Lors de la partition suivant le pivot x, le nombre de comparaisons faisant intervenir x
est donc le même que lors de la construction de l’arbre binaire de recherche lorsque
la première clé insérée est x. La partition suivant x, lors de l’exécution du tri rapide,
crée deux sous-tableaux dont les valeurs des clés sont exactement celles qui se
12 D’un point de vue informatique, cela se fait en ajoutant des comparaisons d’indices dans les
boucles internes, pour éviter la comparaison d’une clé avec un élément hors des bornes du tableau.
79
Fig. 3.14 En haut, le tableau
T initial, avec le pivot x en
T [0]. En bas, le tableau T à la
fin de l’algorithme de
partition et placement du
pivot x : le pivot est à sa place
définitive T [k], et les deux
sous-tableaux T 1 et T 2 restent
à trier récursivement
Dans un tableau de clés, choisir une clé x comme pivot, trouver sa place définitive dans le
tableau en faisant appel à l’algorithme PARTITION, qui de plus réarrange ledit tableau de
telle sorte que les clés inférieures ou égales à x soient à sa gauche, et les clés supérieures à
sa droite, puis trier récursivement les deux sous-tableaux ainsi créés.
Lien tri rapide – arbre binaire de recherche
Revenons à la version classique du tri rapide. Ce tri agit sur un tableau, c’est-àdire sur une suite de clés : la représentation dans un tableau induit un ordre sur les
clés. Dans ce qui suit, nous allons identifier un tableau de n clés et une suite de la
même taille. Le processus de partitionnement d’un tableau de n clés, suivi d’appels
récursifs sur les sous-tableaux, ressemble beaucoup à la construction statique d’un
arbre binaire de recherche sur le même ensemble de clés.
Pour rendre explicite ce lien entre le tri rapide et les arbres binaires de recherche,
nous allons considérer non pas la version informatique usuelle de l’algorithme
PARTITION, qui est donnée en annexe A.6.1 et qui fait appel à une « sentinelle »,
i.e., à une clé supplémentaire, placée en fin de tableau et servant à éviter de
vérifier systématiquement que l’indice de la case testée est bien dans les bornes du
tableau, mais une version sans sentinelle et où chaque clé du tableau est comparée
exactement une fois au pivot. 12
Regardons alors les comparaisons de clés faites pour placer le pivot, que nous
supposons être la première clé d’un tableau de taille n : ces comparaisons sont entre
le pivot et les autres clés, et il y en a exactement n − 1. De façon parallèle, si nous
construisons un arbre binaire de recherche en insérant les clés dans l’ordre où elles
se présentent dans le tableau, la même clé x qui sert de pivot va se retrouver à la
racine de l’arbre et toutes les autres clés seront comparées exactement une fois à x.
Lors de la partition suivant le pivot x, le nombre de comparaisons faisant intervenir x
est donc le même que lors de la construction de l’arbre binaire de recherche lorsque
la première clé insérée est x. La partition suivant x, lors de l’exécution du tri rapide,
crée deux sous-tableaux dont les valeurs des clés sont exactement celles qui se
12 D’un point de vue informatique, cela se fait en ajoutant des comparaisons d’indices dans les
boucles internes, pour éviter la comparaison d’une clé avec un élément hors des bornes du tableau.