3.3 Tri d’un ensemble de clés
89
Tout d’abord, pour éviter le coût d’appels récursifs sur des tableaux de très petite
taille, disons inférieure à un entier b fixé, nous pouvons choisir d’arrêter le tri sur des
sous-tableaux de taille au plus b (une valeur de l’ordre de 10 semble pertinente en
pratique), et de terminer le tri de tout le tableau par un appel global à la procédure de
tri par insertion. L’arbre en relation avec la première partie de cet algorithme (avant
le tri par insertion) est alors un arbre binaire de recherche paginé, i.e., les sous-arbres
de taille au plus b sont contenus dans un seul nœud. Nous renvoyons à l’article de
Hennequin [128] pour une analyse fine du coût du tri rapide lorsqu’il se termine par
un tri par insertion, et aux résultats de Martinez, Panholzer et Prodinger [181], par
exemple, pour une étude sur la taille des sous-arbres d’un arbre binaire de recherche,
et sur le lien entre ces arbres paginés et les performances du tri rapide.
Pour éviter les sous-tableaux de trop petite taille, il est aussi possible de jouer
sur le choix du pivot : ce ne sera plus le premier (ou le deuxième, ou dernier. . . )
élément du sous-tableau à trier, mais la clé médiane parmi un ensemble de clés (le
plus simple est de prendre = 3, mais des valeurs plus grandes, impaires pour que la
médiane soit définie sans ambiguïté, peuvent s’avérer pertinentes). Chacun des soustableaux créés par la partition est alors de taille au moins
2 . Si un choix de pivot
comme médiane de éléments améliore les performances de PARTITION, il faut
cependant prendre en compte le nombre de comparaisons nécessaires pour trouver
cette médiane ; cf. par exemple Martinez et Roura [180], qui montrent que la valeur
optimale de est d’ordre
√
n. Les arbres binaires de recherche pertinents sont alors
ceux soumis à des réarrangements locaux faisant appel à l’algorithme de rotation
défini en annexe A.1.4 ; une présentation claire du lien entre ces arbres et le choix
du pivot comme médiane de plusieurs éléments se trouve dans Hennequin [129,
Ch. 2].
Si le tableau à trier comporte beaucoup d’éléments répétés, il peut être intéressant
de remplacer l’algorithme PARTITION, qui divise un ensemble de clés en deux
parties, suivant qu’elles sont inférieures ou égales, ou bien supérieures, au pivot,
par l’algorithme connu sous le nom de « drapeau hollandais ». Cet algorithme
partitionne l’ensemble des clés en trois parties, en distinguant les clés inférieures
au pivot de celles qui lui sont égales. Hennequin [129, Ch. 5] présente une analyse
détaillée du tri rapide dans le cas de prise en compte des répétitions de clés,
pour plusieurs algorithmes de partition. Sur les arbres binaires de recherche, la
variante qui utilise le drapeau hollandais pour la partition pourrait correspondre à
l’algorithme d’insertion dans laquelle les clés égales sont insérées consécutivement,
le nombre de clés égales à une clé x choisie comme pivot étant la longueur de la
branche qui mène alors au premier 17 nœud, dans le sous-arbre gauche, étiqueté par
une clé strictement inférieure à x.
Une autre possibilité en ce qui concerne le pivot est d’en prendre, non pas
un, mais deux ; c’est par exemple ce qui est fait dans la version du tri rapide
actuellement implémentée en Java (voir par exemple Martinez, Nebel et Wild [183]
pour une analyse fine de ses performances). La modification porte là encore sur
17 pour l’ordre préfixe.
89
Tout d’abord, pour éviter le coût d’appels récursifs sur des tableaux de très petite
taille, disons inférieure à un entier b fixé, nous pouvons choisir d’arrêter le tri sur des
sous-tableaux de taille au plus b (une valeur de l’ordre de 10 semble pertinente en
pratique), et de terminer le tri de tout le tableau par un appel global à la procédure de
tri par insertion. L’arbre en relation avec la première partie de cet algorithme (avant
le tri par insertion) est alors un arbre binaire de recherche paginé, i.e., les sous-arbres
de taille au plus b sont contenus dans un seul nœud. Nous renvoyons à l’article de
Hennequin [128] pour une analyse fine du coût du tri rapide lorsqu’il se termine par
un tri par insertion, et aux résultats de Martinez, Panholzer et Prodinger [181], par
exemple, pour une étude sur la taille des sous-arbres d’un arbre binaire de recherche,
et sur le lien entre ces arbres paginés et les performances du tri rapide.
Pour éviter les sous-tableaux de trop petite taille, il est aussi possible de jouer
sur le choix du pivot : ce ne sera plus le premier (ou le deuxième, ou dernier. . . )
élément du sous-tableau à trier, mais la clé médiane parmi un ensemble de clés (le
plus simple est de prendre = 3, mais des valeurs plus grandes, impaires pour que la
médiane soit définie sans ambiguïté, peuvent s’avérer pertinentes). Chacun des soustableaux créés par la partition est alors de taille au moins
2 . Si un choix de pivot
comme médiane de éléments améliore les performances de PARTITION, il faut
cependant prendre en compte le nombre de comparaisons nécessaires pour trouver
cette médiane ; cf. par exemple Martinez et Roura [180], qui montrent que la valeur
optimale de est d’ordre
√
n. Les arbres binaires de recherche pertinents sont alors
ceux soumis à des réarrangements locaux faisant appel à l’algorithme de rotation
défini en annexe A.1.4 ; une présentation claire du lien entre ces arbres et le choix
du pivot comme médiane de plusieurs éléments se trouve dans Hennequin [129,
Ch. 2].
Si le tableau à trier comporte beaucoup d’éléments répétés, il peut être intéressant
de remplacer l’algorithme PARTITION, qui divise un ensemble de clés en deux
parties, suivant qu’elles sont inférieures ou égales, ou bien supérieures, au pivot,
par l’algorithme connu sous le nom de « drapeau hollandais ». Cet algorithme
partitionne l’ensemble des clés en trois parties, en distinguant les clés inférieures
au pivot de celles qui lui sont égales. Hennequin [129, Ch. 5] présente une analyse
détaillée du tri rapide dans le cas de prise en compte des répétitions de clés,
pour plusieurs algorithmes de partition. Sur les arbres binaires de recherche, la
variante qui utilise le drapeau hollandais pour la partition pourrait correspondre à
l’algorithme d’insertion dans laquelle les clés égales sont insérées consécutivement,
le nombre de clés égales à une clé x choisie comme pivot étant la longueur de la
branche qui mène alors au premier 17 nœud, dans le sous-arbre gauche, étiqueté par
une clé strictement inférieure à x.
Une autre possibilité en ce qui concerne le pivot est d’en prendre, non pas
un, mais deux ; c’est par exemple ce qui est fait dans la version du tri rapide
actuellement implémentée en Java (voir par exemple Martinez, Nebel et Wild [183]
pour une analyse fine de ses performances). La modification porte là encore sur
17 pour l’ordre préfixe.