3.3 Tri d’un ensemble de clés
83
x2 < x1
x3 < x1
x3 < x1
1
x
>
4
x
1
x
<
4
x
x4 > x1
x3 > x1
*
1
*
2
*
4
*
3
4
*
*
3
*
*
*
4
non
oui
i
u
o
n
o
n
i
u
o
oui
non
oui
non
oui
non
oui
non
x3 > x1
x2 > x1
2 1 * *
1 * * *
x2 < x1
x3 > x1
x2 > x1
non : echange de T[2]
x4 > x1
2 * * 1
x3 > x1
3 4 * *
Fig. 3.17 L’arbre de décision τ (4, P artition) associé à l’algorithme PARTITION (voir la
section A.6.1) et à une taille n = 4 du tableau T 0 = [x 1 , x 2 , x 3 , x 4 ] à partitionner ; ce tableau est
identifié à un élément σ ∈ S 4 : x 1 = σ (1), x 2 = σ (2), etc. Le pivot de la partition est x 1 = T 0 [1].
Les feuilles sont marquées par les classes d’équivalence de la relation R A . Par exemple, la notation
4 ∗ ∗∗ correspond à la classe des permutations σ associées à un tableau T 0 tel que σ (1) = 4
– Les nœuds internes de τ (n, A) sont marqués par des comparaisons x i < x j .
– Les feuilles sont marquées par les classes d’équivalence de R A .
– Si un nœud interne est marqué par la comparaison x i < x j , l’exécution
de l’algorithme A se poursuit dans le sous-arbre gauche dans le cas où la
comparaison est satisfaite, et dans le sous-arbre droit sinon.
Notons qu’il y a un arbre de décision par algorithme et par taille n des données.
Les branches de τ , ou en d’autres termes les chemins de la racine vers une feuille
de l’arbre, indiquent les comparaisons de clés faites par l’algorithme lors de ses
exécutions sur tous les tableaux de la classe d’équivalence qui marque la feuille.
La figure 3.17 donne l’arbre de décision pour l’algorithme PARTITION qui est
le cœur du tri rapide (voir la section A.6.1), et pour le tableau de 4 clés T [1 . . 4].
Cet arbre peut être étendu, en développant chaque feuille en accord avec les appels
suivants de PARTITION sur les sous-tableaux, pour obtenir l’arbre de décision de
tout le tri rapide.
Comment lire un coût sur un arbre de décision ?
Soit τ = τ (n, A) l’arbre de décision pour un algorithme A et une taille n de données ; la connaissance de τ permet d’obtenir des informations sur le coût de
A, compté en nombre de comparaisons de clés. En effet, chaque exécution de
l’algorithme sur un ensemble de données correspond à une branche de τ arrivant
à une feuille, appelons-la f , et chaque nœud de cette branche correspond à une
comparaison : le coût d’exécution de l’algorithme sur les tableaux appartenant à
83
x2 < x1
x3 < x1
x3 < x1
1
x
>
4
x
1
x
<
4
x
x4 > x1
x3 > x1
*
1
*
2
*
4
*
3
4
*
*
3
*
*
*
4
non
oui
i
u
o
n
o
n
i
u
o
oui
non
oui
non
oui
non
oui
non
x3 > x1
x2 > x1
2 1 * *
1 * * *
x2 < x1
x3 > x1
x2 > x1
non : echange de T[2]
x4 > x1
2 * * 1
x3 > x1
3 4 * *
Fig. 3.17 L’arbre de décision τ (4, P artition) associé à l’algorithme PARTITION (voir la
section A.6.1) et à une taille n = 4 du tableau T 0 = [x 1 , x 2 , x 3 , x 4 ] à partitionner ; ce tableau est
identifié à un élément σ ∈ S 4 : x 1 = σ (1), x 2 = σ (2), etc. Le pivot de la partition est x 1 = T 0 [1].
Les feuilles sont marquées par les classes d’équivalence de la relation R A . Par exemple, la notation
4 ∗ ∗∗ correspond à la classe des permutations σ associées à un tableau T 0 tel que σ (1) = 4
– Les nœuds internes de τ (n, A) sont marqués par des comparaisons x i < x j .
– Les feuilles sont marquées par les classes d’équivalence de R A .
– Si un nœud interne est marqué par la comparaison x i < x j , l’exécution
de l’algorithme A se poursuit dans le sous-arbre gauche dans le cas où la
comparaison est satisfaite, et dans le sous-arbre droit sinon.
Notons qu’il y a un arbre de décision par algorithme et par taille n des données.
Les branches de τ , ou en d’autres termes les chemins de la racine vers une feuille
de l’arbre, indiquent les comparaisons de clés faites par l’algorithme lors de ses
exécutions sur tous les tableaux de la classe d’équivalence qui marque la feuille.
La figure 3.17 donne l’arbre de décision pour l’algorithme PARTITION qui est
le cœur du tri rapide (voir la section A.6.1), et pour le tableau de 4 clés T [1 . . 4].
Cet arbre peut être étendu, en développant chaque feuille en accord avec les appels
suivants de PARTITION sur les sous-tableaux, pour obtenir l’arbre de décision de
tout le tri rapide.
Comment lire un coût sur un arbre de décision ?
Soit τ = τ (n, A) l’arbre de décision pour un algorithme A et une taille n de données ; la connaissance de τ permet d’obtenir des informations sur le coût de
A, compté en nombre de comparaisons de clés. En effet, chaque exécution de
l’algorithme sur un ensemble de données correspond à une branche de τ arrivant
à une feuille, appelons-la f , et chaque nœud de cette branche correspond à une
comparaison : le coût d’exécution de l’algorithme sur les tableaux appartenant à