Revision 5429b2ad5f1120f6fe43bfd15d4ba05cd1517bcc authored by brianharvey on 17 September 2008, 05:01:40 UTC, committed by brianharvey on 17 September 2008, 05:01:40 UTC
git-svn-id: https://svn.code.sf.net/p/ucblogo/code@207 fc4ef4ee-df3e-0410-84de-fb01f5d6c4f7
1 parent a3598a9
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.
![swh spinner](/static/img/swh-spinner.gif)
Computing file changes ...