3.3 Tri d’un ensemble de clés
81
Supposons cependant que les clés du tableau T à trier, que nous supposons toutes
distinctes, soient données par une permutation tirée uniformément dans S n . Nous
donnons ci-dessous une définition formelle de ce modèle. 13
Définition 3.6 Un tableau aléatoire T de taille n est dit suivre la loi des permutations uniformes sur les tableaux lorsque tous ses éléments sont distincts et
que, après renumérotage des n valeurs apparaissant dans T , la suite obtenue suit
la distribution uniforme sur l’ensemble S n des permutations de {1, . . . , n}.
L’arbre binaire de recherche construit à partir de cette suite suit alors le modèle
des permutations uniformes (cf. la définition 2.4). En sommant sur tous les appels
récursifs et toutes les suites possibles, qui définissent aussi bien les tableaux à trier
que les ordres d’insertion pour former l’arbre binaire de recherche, les nombres de
comparaisons de clés faites, d’une part lors du tri rapide d’un tableau, d’autre part
lors de la construction d’un arbre binaire de recherche, sont donc de même loi.
Coût du tri rapide
L’analyse du coût du tri rapide a fait l’objet d’analyses détaillées ; nous renvoyons
aux livres classiques d’algorithmique tels Froidevaux, Gaudel et Soria [111] ou
Sedgewick [231] pour son comportement en moyenne et au pire, et par exemple
à Rösler [224] pour la variance, et résumons les résultats dans la proposition 3.7.
Proposition 3.7 Soit Z n = Z n (T ) le nombre de comparaisons entre clés faites
par l’algorithme de tri rapide pour trier les n clés, supposées distinctes, d’un
tableau T .
i) Le maximum de Z n est d’ordre n 2 ; ce cas est atteint notamment lorsque T est
trié en ordre croissant ou décroissant.
ii) Lorsque T suit la loi des permutations uniformes sur les tableaux (cf. la
définition 3.6), la moyenne de Z n est asymptotiquement équivalente à 2n log n,
et sa variance est asymptotiquement équivalente à (7 − 2π 2 /3) n 2 ; la variable
aléatoire Z n , après normalisation, converge en loi vers une distribution limite.
Remarque 3.8 Ce nombre de comparaisons Z n (T ) a même loi que lc(τ n ), où τ n est
l’arbre binaire de recherche que nous avons associé ci-dessus au tableau T .
Comparons ce que nous apprend la proposition 3.7 sur le nombre de comparaisons de clés faites par l’algorithme de tri rapide, avec le nombre de comparaisons
requis par tout tri par comparaison ; cf. par exemple l’article original de Hoare [131]
ou le livre de Froidevaux, Gaudel et Soria [111, Ch. 16].
Proposition 3.9 Soit A un algorithme de tri procédant par comparaisons et échanges de clés. Appelons Z n (T , A) le nombre de comparaisons faites par l’algorithme
13 qui peut être appelé « modèle des permutations uniformes » à meilleur titre que celui du même
nom relatif aux arbres binaires de recherche !
81
Supposons cependant que les clés du tableau T à trier, que nous supposons toutes
distinctes, soient données par une permutation tirée uniformément dans S n . Nous
donnons ci-dessous une définition formelle de ce modèle. 13
Définition 3.6 Un tableau aléatoire T de taille n est dit suivre la loi des permutations uniformes sur les tableaux lorsque tous ses éléments sont distincts et
que, après renumérotage des n valeurs apparaissant dans T , la suite obtenue suit
la distribution uniforme sur l’ensemble S n des permutations de {1, . . . , n}.
L’arbre binaire de recherche construit à partir de cette suite suit alors le modèle
des permutations uniformes (cf. la définition 2.4). En sommant sur tous les appels
récursifs et toutes les suites possibles, qui définissent aussi bien les tableaux à trier
que les ordres d’insertion pour former l’arbre binaire de recherche, les nombres de
comparaisons de clés faites, d’une part lors du tri rapide d’un tableau, d’autre part
lors de la construction d’un arbre binaire de recherche, sont donc de même loi.
Coût du tri rapide
L’analyse du coût du tri rapide a fait l’objet d’analyses détaillées ; nous renvoyons
aux livres classiques d’algorithmique tels Froidevaux, Gaudel et Soria [111] ou
Sedgewick [231] pour son comportement en moyenne et au pire, et par exemple
à Rösler [224] pour la variance, et résumons les résultats dans la proposition 3.7.
Proposition 3.7 Soit Z n = Z n (T ) le nombre de comparaisons entre clés faites
par l’algorithme de tri rapide pour trier les n clés, supposées distinctes, d’un
tableau T .
i) Le maximum de Z n est d’ordre n 2 ; ce cas est atteint notamment lorsque T est
trié en ordre croissant ou décroissant.
ii) Lorsque T suit la loi des permutations uniformes sur les tableaux (cf. la
définition 3.6), la moyenne de Z n est asymptotiquement équivalente à 2n log n,
et sa variance est asymptotiquement équivalente à (7 − 2π 2 /3) n 2 ; la variable
aléatoire Z n , après normalisation, converge en loi vers une distribution limite.
Remarque 3.8 Ce nombre de comparaisons Z n (T ) a même loi que lc(τ n ), où τ n est
l’arbre binaire de recherche que nous avons associé ci-dessus au tableau T .
Comparons ce que nous apprend la proposition 3.7 sur le nombre de comparaisons de clés faites par l’algorithme de tri rapide, avec le nombre de comparaisons
requis par tout tri par comparaison ; cf. par exemple l’article original de Hoare [131]
ou le livre de Froidevaux, Gaudel et Soria [111, Ch. 16].
Proposition 3.9 Soit A un algorithme de tri procédant par comparaisons et échanges de clés. Appelons Z n (T , A) le nombre de comparaisons faites par l’algorithme
13 qui peut être appelé « modèle des permutations uniformes » à meilleur titre que celui du même
nom relatif aux arbres binaires de recherche !