 |
Le Quick Sort est assez simple à comprendre, mais assez compliqué à transcrire en algorithme. Le Quick Sort consiste à trier un
tableau en le découpant récursivement en 2 sous tableaux, où les éléments du premier tableau sont inférieurs aux éléments du second.
En faisant une opération récursive, on découpe le tableau en élément de plus en plus petit, jusqu'à arriver à un sous tableau à
un seul élément, qui est donc forcément trié. Ensuite, en remontant, les éléments sont triés petit à petit.
L'algorithme se découpe en 2 fonctions : une fonction SPLIT qui s'occupe de réarranger le tableau, et une fonction QUICKSORT qui
gère la récursivité et le découpage en sous tableaux.
Procédure SPLIT (Element : Tableau; K, L, I: Entier)
I <- K
J <- L+1
X <- Element (I)
REPETER
REPETER
J <- J-1
JUSQU'A (Element (J) < X) ou (I = J)
Element (I) <- Element (J)
TANT QUE (I < J) et (Element (I) <= X) FAIRE
I <- I+1
FIN TANT QUE
Element (J) <- Element (I)
JUSQU'A I = J
Element (I) <- X
Fin Procédure
Procédure QUICKSORT (Element: Tableau; K, L: Entier)
SI K < L ALORS
SPLIT (Element , K, L, I)
QUICKSORT (Element, K, I-1)
QUICKSORT (Element, I+1, L)
FIN SI
Fin Procédure
Variables :
| Nom | Fonction |
| I | Compteur correspondant à l'indice du pivot (indice de l'élément qui sépare les sous-tableaux) |
| J | Compteur courant dans le tableau |
| K | Premier indice du tableau |
| L | Dernier indice du tableau |
| X | Valeur du premier élément du tableau |
| Element | Tableau (ou liste, pile...) à trier |
function mysplit(&$TopDest, &$K, &$L, &$I) {
$I = $K;
$J = $L+1;
$X = $TopDest[$I];
do {
do {
$J = $J-1;
}
while (($TopDest[$J] > $X) && ($I <> $J));
$TopDest[$I] = $TopDest[$J];
while (($I < $J) && ($TopDest[$I] <= $X)) {
$I = $I+1;
}
$TopDest[$J] = $TopDest[$I];
}
while ($I != $J);
$TopDest[$I] = $X;
}
function quicksort (&$TopDest, $K, $L) {
if ($K < $L) {
mysplit ($TopDest, $K, $L, $I);
quicksort ($TopDest, $K, $I-1);
quicksort ($TopDest, $I+1, $L);
}
}
Sub split(TopDest(), K, L, I)
dim J
dim X
I = K
J = L+1
X = TopDest(I)
do
do
J = J-1
loop until (TopDest(J) < X) or (I = J)
TopDest(I) = TopDest(J)
do while (I < J) and (TopDest(I) <= X)
I = I+1
loop
TopDest(J) = TopDest(I)
loop until I = J
TopDest(I) = X
end Sub
Sub quicksort (TopDest, K, L)
dim I
if K < L then
split TopDest, K, L, I
quicksort TopDest, K, I-1
quicksort TopDest, I+1, L
end if
end Sub
|
