3.3 Tri d’un ensemble de clés
93
d’opérations (comparaisons ou échanges de clés) est, dans le pire des cas,
proportionnel à la hauteur du tas, et nous avons vu dans l’équation (1.7) que la
hauteur d’un tas de taille n (en fait, de l’arbre parfait sous-jacent) vaut log 2 n
ii) Cela permet ensuite de montrer aisément que le coût du tri par tas dans le
cas le pire, sur un ensemble de n clés, est d’ordre n log 2 n. En effet, prenons
par exemple le nombre d’échanges de clés faits par l’algorithme de tri par
tas lors de la suppression des minima successifs. Avec un tas de taille p, ce
nombre est borné supérieurement par la hauteur du tas, donc par log 2 p
Lorsque nous prenons en compte toutes les étapes, une borne supérieure sur
le nombre d’échanges est obtenue en supposant que nous avons, sur chacun des
tas successifs, le comportement au pire, ce qui conduit à sommer log 2 p sur
toutes les tailles possibles p ∈ {1, . . . , n}, et fournit une borne supérieure égale
à n log 2 n.
iii) Nous avons vu précédemment que le nombre moyen de comparaisons fait
par tout tri par comparaison, lorsque les clés sont prises dans un tableau
correspondant à une permutation uniforme, est au minimum de l’ordre de
n log n (c’est la proposition 3.9). Ceci donne une borne inférieure sur le nombre
de comparaisons faites par le tri par tas sur n clés, qui est d’ordre n log n. Une
borne supérieure sur ce nombre de comparaisons est donnée par le nombre
maximal de comparaisons, et nous venons de voir que ce nombre est également
d’ordre n log n. Le nombre de comparaisons moyen ne peut donc être que
d’ordre n log n.
3.3.4 Tri radix
À la différence du tri rapide et du tri par tas présentés plus haut, le tri radix n’est
plus un tri par comparaison de clés : il utilise une information sur la nature des clés,
ce qui permet d’avoir un tri en temps (pseudo-)linéaire. En fait, il organise les clés
suivant un trie.
Pour les algorithmes de la famille du tri radix, les clés se décomposent en
« morceaux » de taille fixée de telle sorte que chaque « morceau » ne puisse prendre
qu’un nombre fini k de valeurs. Dans le vocabulaire utilisé dans ce livre, cela signifie
que les clés sont des mots et que les morceaux sont des symboles (ou lettres) d’un
alphabet fini de taille k. Une autre manière d’envisager la situation est de considérer
que les clés sont des nombres dans un système de numération en base k (c’est
d’ailleurs l’origine du nom de ce tri). L’alphabet est alors 0, 1, . . . , k − 1.
Plusieurs valeurs de k peuvent être choisies en fonction des applications. En
informatique, les valeurs de k sont en général des puissances de deux. Pour les
chaînes de caractères utilisant un encodage usuel, nous utilisons le plus souvent
k = 2 8 ou k = 2 16 .
Tri radix binaire Un cas d’importance est le cas binaire (k = 2) pour lequel les
clés sont des séquences de bits. Dans ce cas précis, le tri radix est parfois appelé tri
93
d’opérations (comparaisons ou échanges de clés) est, dans le pire des cas,
proportionnel à la hauteur du tas, et nous avons vu dans l’équation (1.7) que la
hauteur d’un tas de taille n (en fait, de l’arbre parfait sous-jacent) vaut log 2 n
ii) Cela permet ensuite de montrer aisément que le coût du tri par tas dans le
cas le pire, sur un ensemble de n clés, est d’ordre n log 2 n. En effet, prenons
par exemple le nombre d’échanges de clés faits par l’algorithme de tri par
tas lors de la suppression des minima successifs. Avec un tas de taille p, ce
nombre est borné supérieurement par la hauteur du tas, donc par log 2 p
Lorsque nous prenons en compte toutes les étapes, une borne supérieure sur
le nombre d’échanges est obtenue en supposant que nous avons, sur chacun des
tas successifs, le comportement au pire, ce qui conduit à sommer log 2 p sur
toutes les tailles possibles p ∈ {1, . . . , n}, et fournit une borne supérieure égale
à n log 2 n.
iii) Nous avons vu précédemment que le nombre moyen de comparaisons fait
par tout tri par comparaison, lorsque les clés sont prises dans un tableau
correspondant à une permutation uniforme, est au minimum de l’ordre de
n log n (c’est la proposition 3.9). Ceci donne une borne inférieure sur le nombre
de comparaisons faites par le tri par tas sur n clés, qui est d’ordre n log n. Une
borne supérieure sur ce nombre de comparaisons est donnée par le nombre
maximal de comparaisons, et nous venons de voir que ce nombre est également
d’ordre n log n. Le nombre de comparaisons moyen ne peut donc être que
d’ordre n log n.
3.3.4 Tri radix
À la différence du tri rapide et du tri par tas présentés plus haut, le tri radix n’est
plus un tri par comparaison de clés : il utilise une information sur la nature des clés,
ce qui permet d’avoir un tri en temps (pseudo-)linéaire. En fait, il organise les clés
suivant un trie.
Pour les algorithmes de la famille du tri radix, les clés se décomposent en
« morceaux » de taille fixée de telle sorte que chaque « morceau » ne puisse prendre
qu’un nombre fini k de valeurs. Dans le vocabulaire utilisé dans ce livre, cela signifie
que les clés sont des mots et que les morceaux sont des symboles (ou lettres) d’un
alphabet fini de taille k. Une autre manière d’envisager la situation est de considérer
que les clés sont des nombres dans un système de numération en base k (c’est
d’ailleurs l’origine du nom de ce tri). L’alphabet est alors 0, 1, . . . , k − 1.
Plusieurs valeurs de k peuvent être choisies en fonction des applications. En
informatique, les valeurs de k sont en général des puissances de deux. Pour les
chaînes de caractères utilisant un encodage usuel, nous utilisons le plus souvent
k = 2 8 ou k = 2 16 .
Tri radix binaire Un cas d’importance est le cas binaire (k = 2) pour lequel les
clés sont des séquences de bits. Dans ce cas précis, le tri radix est parfois appelé tri