6.8 Exercices
277
prenne la valeur j , conditionnée par le fait que le pivot ait le rang k :
P(ν(T ) = j |T [1] = k) =
k−1
j
n−k
j
n−1
k−1
.
Le nombre moyen d’échanges, toujours sachant que le pivot est de rang k, est donc
E(ν(T )|T [1] = k) =
(k − 1)(n − k)
(n − 1)
.
Comme les n rangs possibles du pivot sont équiprobables sous le modèle des
permutations uniformes, le nombre moyen d’échanges ν n s’obtient maintenant
comme
ν n =
1
n
n
k=1
E(ν(T )| le pivot va en T [k])
=
1
n
n
k=1
(k − 1)(n − k)
(n − 1)
=
n − 2
6
.
Soit e(T ) le nombre total d’échanges fait par le tri rapide pour trier un tableau T :
c’est la somme des nombres d’échanges faits par chaque appel de la partition. En
prenant sa moyenne e n sur tous les tableaux T de taille n sous le modèle des
permutations uniformes, sans oublier d’ajouter le dernier échange qui place le pivot,
et parce que chaque sous-tableau obtenu par partition et placement du pivot suit
encore le modèle des permutations uniformes, nous obtenons
e n =
n + 4
6
+
n
k=1
1
n
(e k−1 + e n−k ),
d’où, en sommant, la proposition suivante.
Proposition 6.43 Le nombre moyen e n d’échanges de clés faits par le tri rapide,
sur un tableau de n clés sous le modèle des permutations uniformes, vaut
2n+11
6 .
6.8 Exercices
6.1. Le nombre de permutations de n éléments est n!, et le nombre d’arbres binaires de taille
n est C n = o(n!) ; il est donc clair qu’une forme d’arbre donnée sera obtenue par plusieurs ordres
d’insertion de n clés distinctes dans un arbre initialement vide. Sous le modèle des permutations