program sort;
uses crt;
const maxT=2500;
maxR=1.7e38;
type tablica=array[1..maxT] of real;
poltablica=array[1..maxT div 2+2] of real;
procedure merge(var A:tablica;p,q,r:integer);
var n1,n2,i,j,k:integer;
B,C:poltablica;
begin
n1:=q-p+1;
n2:=r-q;
for i:=p to q do
B[i-p+1]:=A[i];
for i:=q+1 to r do
C[i-q]:=A[i];
B[n1+1]:=maxR;
C[n2+1]:=maxR;
i:=1;
j:=1;
for k:=p to r do
if (B[i]<=C[j]) then
begin
A[k]:=B[i];
i:=i+1;
end
else
begin
A[k]:=C[j];
j:=j+1;
end;
end;
procedure mergesort(var A:tablica;p,r:integer);
var q:integer;
begin
if (p<r) then
begin
q:=(p+r) div 2;
mergesort(A,p,q);
mergesort(A,q+1,r);
merge(A,p,q,r);
end;
end;
var A:tablica;
k,n,p,q:integer;
esc:char;
begin
clrscr;
repeat
randomize;
write('Podaj n=');
readln(n);
for k:=1 to n do
begin
p:=(1-2*random(2))*random(10);
q:=1+random(10);
A[k]:=p/q;
end;
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
mergesort(A,1,n);
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
esc:=readkey;
until esc=#27;
end.
1. Dlaczego Cormen używa wartowników ?
Według mnie są one niepotrzebne i sprawiają że kod jest niepraktyczny
2. Dlaczego używa dwóch tablic pomocniczych zamiast jednej (aby jako tako działało musiałem zdefiniować dwa typy tablicowe)
3. Można było napisać ten kod iteracyjnie
4. Jak przystosować ten kod do sortowania plików tekstowych
program sort;
uses crt;
const maxT=2000;
type tablica=array[1..maxT]of real;
procedure Heapify(var A:tablica;i,heapsize:integer);
var l,r,largest:integer;
temp:real;
begin
l:=2*i;
r:=2*i+1;
if(l<=heapsize)and(A[l]>A[i]) then
largest:=l
else largest:=i;
if(r<=heapsize)and(A[r]>A[largest]) then
largest:=r;
if largest<>i then
begin
temp:=A[i];
A[i]:=A[largest];
A[largest]:=temp;
heapify(A,largest,heapsize);
end;
end;
procedure Buildheap(var A:tablica;len:integer);
var i:integer;
begin
for i:=len div 2 downto 1 do
heapify(A,i,len);
end;
procedure Heapsort(var A:tablica;len:integer);
var i,heapsize:integer;
temp:real;
begin
Buildheap(A,len);
heapsize:=len;
for i:=len downto 2 do
begin
temp:=A[1];
A[1]:=A[i];
A[i]:=temp;
heapsize:=heapsize-1;
Heapify(A,1,heapsize);
end;
end;
var A:tablica;
k,n,p,q:integer;
esc:char;
begin
clrscr;
repeat
randomize;
write('Podaj n=');
readln(n);
for k:=1 to n do
begin
p:=(1-2*random(2))*random(10);
q:=1+random(10);
A[k]:=p/q;
end;
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
Heapsort(A,n);
for k:=1 to n do
write(A[k]:1:10,' ');
writeln;
writeln;
esc:=readkey;
until esc=#27;
end.
Tutaj procedurę Heapify można było napisać interacyjnie
