90
3 Arbres, algorithmes et données
l’algorithme PARTITION, qui doit placer les clés suivant leurs valeurs par rapport
à deux pivots x 1 et x 2 , que nous supposons strictement supérieur à x 1 , et donc
les répartir en trois ensembles : clés inférieures ou égales à x 1 , clés strictement
supérieures à x 1 tout en étant inférieures ou égales à x 2 , et enfin clés strictement
supérieures à x 2 . Tout comme dans le cas précédent, ceci conduit au remplacement
de PARTITION par (une variante de) l’algorithme du drapeau hollandais. Dans un
article récent [13], Aumüller et Dietzfelbinger étudient diverses variantes du tri à
deux pivots, et utilisent un arbre de décision ternaire pour prouver l’optimalité d’une
de ces variantes. Le nombre de pivots n’est d’ailleurs pas limité à 2, cf. de nouveau
Hennequin [129, Ch. 2], ou bien Aumüller et Dietzfelbinger [13]. La traduction du
tri rapide à pivots multiples, en termes d’arbres de recherche, serait un arbre m-aire
de recherche, avec m − 1 le nombre de pivots.
Remarquons que nous nous sommes intéressés au coût du tri rapide, défini en tant
que nombre de comparaisons de clés, mais qu’il est possible de le définir comme
nombre d’échanges de clés, voire d’utiliser une pondération de ces deux mesures.
Tout comme le nombre de comparaisons, le nombre d’échanges peut s’analyser
finement, mais il ne se traduit pas en paramètre sur les arbres sous-jacents.
Enfin il est aussi possible, comme nous l’avons déjà vu pour les arbres binaires
de recherche, de tenir compte du fait que les comparaisons de clés font appel
à un nombre variable de comparaisons entre bits, et de prendre ce nombre de
comparaisons de bits comme mesure de coût. Tout comme pour les arbres de
recherche, nous renvoyons aux articles de Fill et al. [77, 246] pour cette mesure
de coût.
3.3.2 Recherche par rang
L’algorithme de recherche par rang rapide («quickselect» en anglais) permet de
trouver « rapidement » une clé de rang donné dans un tableau non trié (en modifiant
cependant partiellement l’ordre des clés du tableau) ; il utilise l’algorithme de
partition et placement du pivot du tri rapide, mais fait ensuite un seul appel récursif,
contre deux pour le tri rapide. Supposons que nous cherchions la p-ième clé du
tableau : nous commençons par faire un appel à PARTITION et le pivot va à la
place k (cf. la figure 3.14). Dans ce qui suit, nous supposons que les indices du
tableau commencent à 0.
– Si k = p − 1, alors nous avons trouvé la p-ième clé, et l’algorithme se termine.
– Si k ≥ p, alors la p-ième clé se trouve dans le sous-tableau de gauche, et
l’algorithme se poursuit récursivement dans ce sous-tableau.
– De façon analogue, si k < p − 1 l’algorithme se poursuit dans le sous-tableau de
droite.
L’algorithme complet est donné en section A.6.2.
Comme pour le tri rapide, nous pouvons établir une relation entre les performances de cet algorithme et celles d’un algorithme de recherche d’une clé dans
3 Arbres, algorithmes et données
l’algorithme PARTITION, qui doit placer les clés suivant leurs valeurs par rapport
à deux pivots x 1 et x 2 , que nous supposons strictement supérieur à x 1 , et donc
les répartir en trois ensembles : clés inférieures ou égales à x 1 , clés strictement
supérieures à x 1 tout en étant inférieures ou égales à x 2 , et enfin clés strictement
supérieures à x 2 . Tout comme dans le cas précédent, ceci conduit au remplacement
de PARTITION par (une variante de) l’algorithme du drapeau hollandais. Dans un
article récent [13], Aumüller et Dietzfelbinger étudient diverses variantes du tri à
deux pivots, et utilisent un arbre de décision ternaire pour prouver l’optimalité d’une
de ces variantes. Le nombre de pivots n’est d’ailleurs pas limité à 2, cf. de nouveau
Hennequin [129, Ch. 2], ou bien Aumüller et Dietzfelbinger [13]. La traduction du
tri rapide à pivots multiples, en termes d’arbres de recherche, serait un arbre m-aire
de recherche, avec m − 1 le nombre de pivots.
Remarquons que nous nous sommes intéressés au coût du tri rapide, défini en tant
que nombre de comparaisons de clés, mais qu’il est possible de le définir comme
nombre d’échanges de clés, voire d’utiliser une pondération de ces deux mesures.
Tout comme le nombre de comparaisons, le nombre d’échanges peut s’analyser
finement, mais il ne se traduit pas en paramètre sur les arbres sous-jacents.
Enfin il est aussi possible, comme nous l’avons déjà vu pour les arbres binaires
de recherche, de tenir compte du fait que les comparaisons de clés font appel
à un nombre variable de comparaisons entre bits, et de prendre ce nombre de
comparaisons de bits comme mesure de coût. Tout comme pour les arbres de
recherche, nous renvoyons aux articles de Fill et al. [77, 246] pour cette mesure
de coût.
3.3.2 Recherche par rang
L’algorithme de recherche par rang rapide («quickselect» en anglais) permet de
trouver « rapidement » une clé de rang donné dans un tableau non trié (en modifiant
cependant partiellement l’ordre des clés du tableau) ; il utilise l’algorithme de
partition et placement du pivot du tri rapide, mais fait ensuite un seul appel récursif,
contre deux pour le tri rapide. Supposons que nous cherchions la p-ième clé du
tableau : nous commençons par faire un appel à PARTITION et le pivot va à la
place k (cf. la figure 3.14). Dans ce qui suit, nous supposons que les indices du
tableau commencent à 0.
– Si k = p − 1, alors nous avons trouvé la p-ième clé, et l’algorithme se termine.
– Si k ≥ p, alors la p-ième clé se trouve dans le sous-tableau de gauche, et
l’algorithme se poursuit récursivement dans ce sous-tableau.
– De façon analogue, si k < p − 1 l’algorithme se poursuit dans le sous-tableau de
droite.
L’algorithme complet est donné en section A.6.2.
Comme pour le tri rapide, nous pouvons établir une relation entre les performances de cet algorithme et celles d’un algorithme de recherche d’une clé dans