swh:1:snp:7c21d1ef6b1a940ffbcf193284a7f8d0c51062e7
Tip revision: 91f307bf5a2820657281457f48cee2ee0073df6f authored by Barak A. Pearlmutter on 16 January 2021, 09:16:31 UTC
oops forgot a dependency
oops forgot a dependency
Tip revision: 91f307b
psort
program psort;
{partition sort demo}
var data: array [0..100] of integer;
i: integer;
procedure showdata;
{print the array}
var i: integer;
begin {showdata}
for i := 0 to 99 do
begin
if i mod 20 = 0 then writeln;
write(data[i]:3)
end;
writeln;
writeln
end; {showdata}
function median(lower,upper:integer):integer;
{find the median of three values from the data array}
var mid: integer;
begin
mid := (lower+upper) div 2;
if (data[lower] <= data[mid]) and (data[mid] <= data[upper]) then
median := mid
else if (data[lower] >= data[mid]) and
(data[mid] >= data[upper]) then
median := mid
else if (data[mid] <= data[lower]) and
(data[lower] <= data[upper]) then
median := lower
else if (data[mid] >= data[lower]) and
(data[lower] >= data[upper]) then
median := lower
else median := upper
end;
procedure sort(lower,upper:integer);
{sort part of the array}
var key,i,j:integer;
procedure exch(var a,b:integer);
{exchange two integers}
var temp:integer;
begin {exch}
temp := a;
a := b;
b := temp
end; {exch}
begin {sort}
if upper > lower then
begin
exch (data[lower],data[median(lower,upper)]);
key := data[lower];
i := lower;
j := upper+1;
repeat
i := i+1
until data[i] >= key;
repeat
j := j-1
until data[j] <= key;
while (i <= j) do
begin
exch(data[i], data[j]);
repeat
i := i+1
until data[i] >= key;
repeat
j := j-1
until data[j] <= key
end;
exch(data[lower], data[j]);
sort(lower,j-1);
sort(i,upper)
end
end; {sort}
begin {main program}
data[100] := 200;
for i := 0 to 99 do
data[i] := random(100);
writeln('Data before sorting:');
showdata;
sort(0,99);
writeln('Data after sorting:');
showdata
end.