Quick sort

Il s'agit d'une méthode de tri récursive dont l'efficacité est une fonction croissante du désordre dans le tableau à trier, c’est à dire que plus le tableau est désordonné, plus cette méthode de tri est efficace.

Algorithme du programme QuickSort

Variables globales :

t : le tableau à trier.

Pour l'exemple, nous prendrons t=(3,5,2,4,6,1,4,10), tableau à 8 éléments.

Paramètres :

debut : l'indice du premier élément du tableau à trier,

fin : l'indice du dernier élément du tableau à trier.

Variables locales :

pivot : l'indice de l'élément qui sert de pivot, comme nous allons l'expliquer plus loin,

gauche : l'indice de l'élément en cours de comparaison avec le pivot, situé avant le pivot,

droite : l'indice de l'élément en cours de comparaison avec le pivot, situé après le pivot,

temp : variable tampon juste pour faire l'échange de deux éléments du tableau.

Principe

On appelle la procédure QuickSort en lui passant en paramètres les indices du premier et du dernier élément du tableau à trier : QuickSort(1,8).

On choisit un élément du tableau au hasard. Ce peut être n'importe lequel. Ici, nous choisissons le premier élément du tableau : 3. L'indice de cet élément est appelé le pivot (ici, c'est 1).

On initialise gauche à début (ici, 1) et droite à fin (ici, 8).

La première partie du travail consiste à ranger le tableau de telle sorte que tous les éléments inférieurs à l'élément d'indice pivot se trouvent placés à la gauche de celui-ci (et donc tous les éléments supérieurs à sa droite).

Ceci se fait par comparaisons et échanges successifs :

repeat

if t[gauche]>=t[droite] then

begin //échanger t[droite] et t[gauche]

temp:=t[gauche];

t[gauche]:=t[droite];

t[droite]:=temp;

pivot:=gauche+droite-pivot; //nouvelle position du pivot

end;

if pivot=gauche then dec(droite) else inc(gauche);

until gauche=droite;

Nous comparons d'abord le premier élément du tableau (3) avec le dernier (10).

Comme 3<10, nous ne faisons rien (donc on a encore pivot=gauche) et nous comparons 3 avec l'avant-dernier élément (dec(droite))du tableau (4).

Comme 3<4, nous ne faisons rien (donc on a encore pivot=gauche) et nous comparons 3 avec l'élément d'indice 6 (dec(droite))du tableau (1).

Comme 3>1, nous échangeons les deux éléments afin que 1 se retrouve à gauche de 3 :

3 5 2 4 6 1 4 10

1 5 2 4 6 3 4 10

Comme pivot désigne maintenant un nouvel emplacement (3 est maintenant en sixième position), nous notons celui-ci : pivot:=gauche+droite-pivot;. Ceci est un raccourci élégant pour if pivot=gauche then pivot:=droite else pivot:=gauche;. En effet, pivot est alors égal à droite ou à gauche car pivot était égal avant à gauche ou à droite.

pivot étant maintenant égal à droite, nous augmentons gauche d'une unité (inc(gauche)) car 1 est désormais placé à gauche de 3 et nous n'avons plus à nous en occuper. A ce stade, gauche=2, pivot=droite=6. Comme gauche est différent de droite, nous continuons.

Comme 5>3, nous échangeons les deux éléments afin que 5 se retrouve à droite de 3 :

1 5 2 4 6 3 4 10

1 3 2 4 6 5 4 10

Comme pivot désigne maintenant un nouvel emplacement (3 est maintenant en deuxième position), nous notons celui-ci : pivot:=gauche+droite-pivot=gauche=2;.

pivot étant maintenant égal à gauche, nous diminuons droite d'une unité (dec(droite)) car 5 est désormais placé à droite de 3 et nous n'avons plus à nous en occuper. A ce stade, gauche=pivot=2, droite=5. Comme gauche est différent de droite, nous continuons.

Comme 3<6, nous ne faisons rien (donc on a encore pivot=gauche) et nous comparons 3 avec l'élément d'indice 4 (dec(droite))du tableau (4).

Comme 3<4, nous ne faisons rien (donc on a encore pivot=gauche) et nous comparons 3 avec l'élément d'indice 3 (dec(droite))du tableau (2).

Comme 3>2, nous échangeons les deux éléments afin que 2 se retrouve à gauche de 3 :

1 3 2 4 6 5 4 10

1 2 3 4 6 5 4 10

Comme pivot désigne maintenant un nouvel emplacement (3 est maintenant en troisième position), nous notons celui-ci : pivot:=gauche+droite-pivot=droite=3;.

pivot étant maintenant égal à droite, nous augmentons gauche d'une unité (inc(gauche)) car 2 est désormais placé à gauche de 3 et nous n'avons plus à nous en occuper. A ce stade, gauche=3, pivot=droite=3. Comme gauche est égal à droite, nous sortons de la boucle repeat/until et nous avons terminé la première phase du travail.

Le tableau est maintenant divisé en deux parties par l'élément d'indice pivot (3) :

1 2

et :

4 6 5 4 10

Les éléments de la partie gauche sont tous inférieurs à 3 et ceux de la partie droite lui sont tous supérieurs. C'est le but que nous nous étions fixé.

Il ne reste plus qu'à laisser opérer la magie de la récursivité, c'est à dire à appeler à nouveau (récursivement) notre procédure QuickSort pour chacun des deux sous-tableaux !

Comme debut<gauche-1 (1<3-1), c'est ce que nous nous empressons de faire avec QuickSort(1,2), et avec QuickSort(4,8), puisque fin>droite+1 (8>3+1) !

L'appel à QuickSort sur la partie gauche n'amènera pas de modification puisque le sous-tableau gauche est déjà trié.

L'appel à QuickSort sur la partie droite conduira à deux échanges pour placer le 6 avant le 10, qui suffiront à terminer le tri. En cours de chemin, il y aura deux sous-appels (inutiles !) à QuickSort qui n'amèneront donc pas de modifications.

Code de la procédure (récursive) QuickSort

procedure QuickSort(debut, fin: integer);
var pivot, gauche, droite, temp: integer;
begin
 pivot := debut;
 gauche := debut;
 droite := fin;
 repeat
 if t[gauche] >= t[droite] then
 begin //échanger t[droite] et t[gauche]
 temp := t[gauche];
 t[gauche] := t[droite];
 t[droite] := temp;
 pivot := gauche + droite - pivot; //nouvelle position du pivot
 //pivot est alors égal à droite ou à gauche car pivot était égal
 //avant à gauche ou à droite.
 //c'est un raccourci élégant pour "if pivot=gauche then pivot:=droite else pivot:=gauche;"
 end;
 if pivot = gauche then dec(droite) else inc(gauche);
 until gauche = droite;
 if debut < gauche - 1 then QuickSort(debut, gauche - 1); //appel récursif sur la partie gauche
 if fin > droite + 1 then QuickSort(droite + 1, fin); //appel récursif sur la partie droite
end;

Télécharger le code source Delphi