Exemple de programmation

en langage Pascal

de QuickSort

(Hoare, 1962)

 

program QuickSort (input, output);

const

MAX = 500;

MIN = 0;

type

myArray = array [MIN..MAX] of integer;

var

vect : myArray;

(*---------------------------------------------------------------------------*)

procedure echanger(var vect : myArray;i ,j : integer) ;

var

temp : integer;

begin

temp := vect [i];

vect [i] := vect [j];

vect[j] := temp;

end;

 

procedure triRapide ( var vect : myArray ; gauche, droit : integer ) ;

var

i, dernier : integer;

begin

if(gauche<droit) then

begin

echanger(vect,gauche,(gauche+droit) div 2);

dernier := gauche;

for i:=gauche+1 to droit do

if (vect[i]<vect[gauche]) then

echanger(vect,++dernier,i);

echanger(vect,gauche,dernier);

triRapide(vect,gauche,dernier-1);

triRapide(vect,dernier+1,droit);

end ;

end;

 

procedure display (vect : myArray;i ,j : integer) ;

var

k : integer;

begin

writeln('Display');writeln;

for k := i to j do

write(' ',vect[k],' ');

writeln;

end;

procedure storage (var vect : myArray;i ,j : integer) ;

var

k : integer;

begin

writeln('Storage');writeln;

for k := i to j do

readln(vect[k]);

writeln;

end;

(*---------------------------------------------------------------------------*)

begin

storage(vect,0,9);

display(vect,0,9);

triRapide(vect,0,9);

display(vect,0,9);

end.

/* ok c'est terminé */

Exemple

Valeur	3	8	5	4	7	6	2	9
Indice	1	2	3	4	5	6	7	8

echanger(v,gauche,(gauche+droit)/2);

Valeur	4	8	5	3	7	6	2	9
Indice	1	2	3	4	5	6	7	8

i=2;dernier=1

for i:=gauche+1 to droit do

if (vect[i]<vect[gauche]) then

echanger(vect,++dernier,i);

 

de i=2 à 3 inclu rien

Pour i=4

Valeur	4	3	5	8	7	6	2	9
Indice	1	2	3	4	5	6	7	8

 

 

de i=5 à 6 inclu rien

Pour i=7

Valeur	4	3	2	8	7	6	5	9
Indice	1	2	3	4	5	6	7	8

 

 

 

echanger(v,gauche,dernier);

Valeur	2	3	4	8	7	6	5	9
Indice	1	2	3	4	5	6	7	8

 

Conclusion:

On voit alors que entre les indices 1 et 3 inclu sont tous les éléments <= à 4, entre 4 et 8 inclu tous les éléments > à 4.