6.7 Un algorithme proche : le tri rapide
273
6.7.1 Modèle probabiliste et paramètres de coût
Fixons la taille n d’un tableau T , et supposons que toutes les clés de T sont
distinctes ; par marquage canonique nous pouvons supposer que ce sont les entiers
1, . . . , n. Une instance de T est en bijection avec une permutation σ ∈ S n , par
T [i] = σ (i), et nous identifions dans la suite un tableau avec une permutation.
Prenons par exemple n = 7 ; la permutation σ = 5 2 7 1 6 4 3 est identifiée au
tableau T = [5, 2, 7, 1, 6, 4, 3]. Nous nous plaçons sous le modèle des permutations
uniformes que nous avons introduit dans la définition 3.6, dans lequel les n! tableaux
possibles sont équiprobables.
Quelle est la mesure de complexité adéquate pour évaluer le coût du tri rapide ?
À la différence des arbres binaires de recherche pour lesquels nous ne prenions en
compte que le nombre de comparaisons entre clés pour déterminer le coût d’un
algorithme, nous avons ici deux mesures possibles : le nombre de comparaisons
entre clés, mais aussi le nombre d’échanges de clés ; nous allons les considérer tous
deux.
La brique de base pour analyser le coût du tri rapide est le coût d’une exécution
de l’algorithme de partition ; ce coût se mesure en nombre d’opérations sur les clés
(comparaisons et échanges). Interviennent ensuite le nombre d’appels récursifs à la
procédure de tri, i.e., à la procédure de partition puisque chaque exécution du tri
rapide sur un tableau de taille ≥ 2 commence par la partition du tableau suivant un
pivot, et la somme des coûts de partition, cumulée sur tous les sous-tableaux.
6.7.2 Nombre moyen de comparaisons de clés
Regardons ce qui se passe lors de l’exécution de l’algorithme de partition, tel que
donné en section A.6.1, sur un tableau de taille n. Les comparaisons se font entre le
pivot x = T [1] et les autres clés du tableau ; elles sont toutes comparées une seule
fois au pivot, sauf éventuellement à la toute fin de la partition, où il peut arriver
que deux clés soient chacune comparée deux fois au pivot lorsque les indices bas et
haut se croisent. Le nombre de comparaisons de clés est donc égal, soit à n − 1, soit
à n + 1.
Soient p(T ) et c(T ) les nombres de comparaisons entre clés faits respectivement
par la procédure de partition et par l’algorithme de tri sur un tableau T . Soient
respectivement p n et c n les moyennes de ces nombres de comparaisons sur tous les
tableaux de taille n suivant la loi des permutations uniformes :
p n =
T ∈S n
p(T )
1
n!
;
c n =
T ∈S n
c(T )
1
n!
.
Les valeurs initiales sont c 0 = c 1 = p 0 = p 1 = 0.
273
6.7.1 Modèle probabiliste et paramètres de coût
Fixons la taille n d’un tableau T , et supposons que toutes les clés de T sont
distinctes ; par marquage canonique nous pouvons supposer que ce sont les entiers
1, . . . , n. Une instance de T est en bijection avec une permutation σ ∈ S n , par
T [i] = σ (i), et nous identifions dans la suite un tableau avec une permutation.
Prenons par exemple n = 7 ; la permutation σ = 5 2 7 1 6 4 3 est identifiée au
tableau T = [5, 2, 7, 1, 6, 4, 3]. Nous nous plaçons sous le modèle des permutations
uniformes que nous avons introduit dans la définition 3.6, dans lequel les n! tableaux
possibles sont équiprobables.
Quelle est la mesure de complexité adéquate pour évaluer le coût du tri rapide ?
À la différence des arbres binaires de recherche pour lesquels nous ne prenions en
compte que le nombre de comparaisons entre clés pour déterminer le coût d’un
algorithme, nous avons ici deux mesures possibles : le nombre de comparaisons
entre clés, mais aussi le nombre d’échanges de clés ; nous allons les considérer tous
deux.
La brique de base pour analyser le coût du tri rapide est le coût d’une exécution
de l’algorithme de partition ; ce coût se mesure en nombre d’opérations sur les clés
(comparaisons et échanges). Interviennent ensuite le nombre d’appels récursifs à la
procédure de tri, i.e., à la procédure de partition puisque chaque exécution du tri
rapide sur un tableau de taille ≥ 2 commence par la partition du tableau suivant un
pivot, et la somme des coûts de partition, cumulée sur tous les sous-tableaux.
6.7.2 Nombre moyen de comparaisons de clés
Regardons ce qui se passe lors de l’exécution de l’algorithme de partition, tel que
donné en section A.6.1, sur un tableau de taille n. Les comparaisons se font entre le
pivot x = T [1] et les autres clés du tableau ; elles sont toutes comparées une seule
fois au pivot, sauf éventuellement à la toute fin de la partition, où il peut arriver
que deux clés soient chacune comparée deux fois au pivot lorsque les indices bas et
haut se croisent. Le nombre de comparaisons de clés est donc égal, soit à n − 1, soit
à n + 1.
Soient p(T ) et c(T ) les nombres de comparaisons entre clés faits respectivement
par la procédure de partition et par l’algorithme de tri sur un tableau T . Soient
respectivement p n et c n les moyennes de ces nombres de comparaisons sur tous les
tableaux de taille n suivant la loi des permutations uniformes :
p n =
T ∈S n
p(T )
1
n!
;
c n =
T ∈S n
c(T )
1
n!
.
Les valeurs initiales sont c 0 = c 1 = p 0 = p 1 = 0.