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 ?
Sortowania
Otrzymałeś(aś) rozwiązanie do zamieszczonego zadania? - podziękuj autorowi rozwiązania! Kliknij
-
- Fachowiec
- Posty: 985
- Rejestracja: 18 paź 2010, 20:45
- Podziękowania: 509 razy
- Otrzymane podziękowania: 4 razy
- Płeć:
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.
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.
-
- Czasem tu bywam
- Posty: 149
- Rejestracja: 30 wrz 2012, 20:36
- Podziękowania: 2 razy
- Otrzymane podziękowania: 13 razy
- Płeć:
Re: Sortowania
Może i są jasne ale kod napisany na ich podstawie jest nieefektywny
a w przypadku sortowania przez scalanie to jest także niepraktyczny
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
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.
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