Sortowania

[Robakks]

Cormen w swoich książkach (Introduction to algorithms , Algotithms unlocked)
komplikuje pseudokod procedur sortujących

W przypadku sortowania przez kopcowanie niepotrzebnie daje w procedurze przywracającej własność kopca rekurencję ogonową
W przypadku sortowania przez scalanie daje wartowników w procedurze scalającej a
procedurę sortującą zostawia w postaci rekurencyjnej

Nie wiem też czemu większość podnieca się quick sortem skoro nie gwarantuje on zatrzymania się w rozsądnym czasie
Trudniej jest także usunąć rekurencje niż w przypadku sortowania przez kopcowanie czy sortowania przez scalanie
(niektórzy nie akceptują rozwiązania z własnym stosem)


Macie propozycje jak poprawić pseudokod Cormena ?

Może napiszecie pseudokod do sortowania listy czy pliku ?

[tukan]

Wg mnie te pseudokody są bardzo jasne, ale to subiektywna opinia. Natomiast to co mnie zainteresowało to dlaczego ludzie podniecają się sortowaniem szybkim.

Jest kilka powodów.
Gdy działa optymalnie jego stała to 1. Gdy działa w przypadku średnim (a więc często) jego stała jest też bardzo zadowalająca - ~1.4
Natomiast stała dla HeapSorta to 2. Pamiętajmy też, że HeapSort może jest w miejscu, ale tam mamy skoki po tablicy, co nie sprzyja cachowaniu tablicy w pamięci podręcznej. Ogólnie to temat na dłuższą dyskusję.

Jak dołożysz algorytm magicznych piątek do HeapSorta to wtedy masz zawsze gwarancję czasy nlogn.
Tak więc QuickSort gwarantuje zatrzymanie się w rozsądnym czasie.

[Robakks]

Może i są jasne ale kod napisany na ich podstawie jest nieefektywny
a w przypadku sortowania przez scalanie to jest także niepraktyczny

Kod: Zaznacz cały

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.

Kod: Zaznacz cały

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.

Jeśli chodzi o sortowanie przez scalanie to
1 Po co mu wartownicy
2. Dlaczego używa dwóch tablic pomocniczych zamiast jednej
3. Można ten kod zapisać iteracyjnie

Jeśli chodzi o sortowanie przez kopcowanie
to po co mu ta rekurencja

Ciekaw jestem jak zamienić rekurencję na pętlę tak aby wyjście z niej było sterowane przez
warunek logiczny bez wyskakiwania z niej instrukcją break