A Rappels algorithmiques
439
Fig. A.24 État du tableau T lors de l’exécution de partitionner(T, 1, n), juste avant la
dernière instruction échanger(T[gauche], T[haut]). La sentinelle est en T[n+1]
tableau T, contenant n clés, a donc une case supplémentaire T[n+1] qui contient la
sentinelle (figure A.24).
Fonction partition(tableau T, entier gauche, entier droite)
// Précondition : 0 ≤ gauche ≤ droite ≤ n + 1 ; pour tout j , 1 ≤ j ≤ n,
T[j ] < T[n + 1].
// Postcondition : Retourne k ∈ [gauche, droite] et le tableau T
partiellement réorganisé entre les indices gauche et droite : la valeur
initiale de T[gauche] est maintenant en T[k] et T[gauche . . k − 1] ≤
T[k] < T[k + 1 . . droite].
// Utilise : échanger
// Variables locales : entier bas, entier haut
bas = gauche + 1
haut = droite
tant que bas ≤ haut faire
tant que T[bas] ≤ T[gauche] faire
bas = bas+1
tant que T[haut] > T[gauche] faire
haut = haut - 1
si bas < haut alors
échanger(T[bas], T[haut])
bas = bas + 1
haut = haut - 1
échanger(T[gauche], T[haut])
retourner haut, T
A.6.2 Recherche par rang
La procédure de partition et placement du pivot est aussi à la base d’un algorithme
de recherche par rang, aussi appelé algorithme de sélection (et connu en anglais
sous le nom de QuickSelect). Il s’agit ici de trouver une clé de rang donné r dans un
tableau non trié de clés.
439
Fig. A.24 État du tableau T lors de l’exécution de partitionner(T, 1, n), juste avant la
dernière instruction échanger(T[gauche], T[haut]). La sentinelle est en T[n+1]
tableau T, contenant n clés, a donc une case supplémentaire T[n+1] qui contient la
sentinelle (figure A.24).
Fonction partition(tableau T, entier gauche, entier droite)
// Précondition : 0 ≤ gauche ≤ droite ≤ n + 1 ; pour tout j , 1 ≤ j ≤ n,
T[j ] < T[n + 1].
// Postcondition : Retourne k ∈ [gauche, droite] et le tableau T
partiellement réorganisé entre les indices gauche et droite : la valeur
initiale de T[gauche] est maintenant en T[k] et T[gauche . . k − 1] ≤
T[k] < T[k + 1 . . droite].
// Utilise : échanger
// Variables locales : entier bas, entier haut
bas = gauche + 1
haut = droite
tant que bas ≤ haut faire
tant que T[bas] ≤ T[gauche] faire
bas = bas+1
tant que T[haut] > T[gauche] faire
haut = haut - 1
si bas < haut alors
échanger(T[bas], T[haut])
bas = bas + 1
haut = haut - 1
échanger(T[gauche], T[haut])
retourner haut, T
A.6.2 Recherche par rang
La procédure de partition et placement du pivot est aussi à la base d’un algorithme
de recherche par rang, aussi appelé algorithme de sélection (et connu en anglais
sous le nom de QuickSelect). Il s’agit ici de trouver une clé de rang donné r dans un
tableau non trié de clés.