6.7 Un algorithme proche : le tri rapide
275
Pour aller plus loin, il nous faut la loi de p n . Or nous ne l’avons pas explicitée ; nous
avons juste mentionné que p n appartient à l’ensemble {n − 1, n + 1}. En prenant p n
toujours égal à n + 1, nous obtenons un majorant c +
n vérifiant :
c +
n
n + 1
=
c
+
n−1
n
+
2
n + 1
(n ≥ 3),
qui se résout en
c +
n
n + 1
= 2H n+1 −
8
3
,
et finalement
c
+
n = 2(n + 1)H n −
8n + 2
3
= 2n log n +
2γ −
8
3
n + O(log n),
avec γ = 0,5772156649 . . . la constante d’Euler. Le même calcul, conduit avec la
borne inférieure c −
n obtenue pour p n = n − 1, donne
c
−
n = 2(n + 1)H n −
10n + 2
3
= 2n log n +
2γ −
10
3
n + O(log n),
donc le même terme principal, qui est par conséquent aussi celui de c n .
Proposition 6.42 Sous le modèle des permutations uniformes, le nombre moyen c n
de comparaisons de clés faites par le tri rapide sur un tableau de n clés est tel que
2(n + 1)H n −
10n + 2
3
≤ c n ≤ 2(n + 1)H n −
8n + 2
3
.
Asymptotiquement lorsque n → +∞, c n = 2n log n + O(n).
Nous ne poussons pas plus loin les calculs : pour avoir le second terme du
développement asymptotique de c n , et non un encadrement comme ici, il nous
faudrait connaître la loi de p n .
6.7.3 Nombre d’échanges de clés
Revenons à une exécution de la partition suivant le pivot T [1], et supposons qu’il
aille à la place k, i.e. que T [1] = k dans le tableau avant partition. Les échanges
se font entre une clé supérieure au pivot et qui est dans le sous-tableau T [2 . . k]
et une clé inférieure au pivot et qui est dans le sous-tableau T [k + 1 . . n]. Un