Cormen sortowanie

Question

    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


 

 

Comments

Jeśli chodzi o sortowanie przez scalanie to z punktami 1. oraz 2.

jakoś sobie poradziłem ale nadal ciekawy jestem jak pozbyć się rekurencji

Co do sortowania stogowego to jaki warunek logiczny wymyślić na pętlę
zastępującą rekurencję aby z tej pętli nie wyskakiwać instrukcjami break