🚀 go-pugleaf

In article <4et6u0$k...@bnet.fuw.edu.pl> Radio ESKA <es...@pol.pl> writes:
>Chce posortowac alfabetycznie liste (z dokl. do n-miejsca)

Kilka algorytmow sortowania jest omowionych w ksiazce Niklausa
Wirtha "Algorytmy + struktury danych = programy", wyglada na to,
ze jezeli dane mieszcza sie w pamieci, to najszybciej dziala
sortowanie stogowe (heapsort), a nie quicksort. Jak sie nie
mieszcza, to sortowanie przez laczenie...

>Jak na razie udalo mi sie tylko do 1 miejsca i dalej zglupialem.

A moze Pan porownuje tylko pierwszy znak klucza?

A tak w ogole, to podobno calkiem niezly jest Radix Sort, nie
wymaga porownywania, tylko wybierania, najpierw rozdzielic na
to, co na n-tej pozycji ma A,B,C...Z i zlozyc po kolei, potem
to samo dla n-1-szej... w koncu dla 1-szej.
Tyle, ze to 2n kopiowan wszystkich danych, troche duzo...

Jerzy Tarasiuk wrote:

> Moze to i kwestia optymalizacji przez kompilator, tak mi wyszlo
> z testowania, dla losowych danych quick sort byl zwykle nieco
> wolniejszy, czasem troche szybszy, a czasem sporo wolniejszy.
> Nie badalem dlaczego, i tak quick sort ma bardzo powazna wade -
> mozliwosc wystapienia najgorszego przypadku, malo prawdopodobna,
> ale za to przy duzych danych trzeba resetowac PC, chybam ze sie
> komus chce czekac iles godzin na zakonczenie sortowania...

Ostatnio z algorytmow pisalem kolokwium, i nawet zaliczylem, to
moze sie wypowiem :)

Co do heapsort to pesymistyczny czas dzialania jest O(n*log(n)),
gdzie n to rozmiar danych. ( Czyli zawsze wykonamy <= jakas stala *
n * log n operacji porownywania i przestwiania )
Quicksort ma pesymistyczny czas O( n^2 ), ktory wystapi tylko przy
bardzo zlosliwych danych. Poza tym, w quicksort mozna wprowadzic
usprawnienie ( zle jest wtedy, gdy dokonywane podzialy nie sa optymalne;
czyli jezeli zawsze dokonywac podzialu pol na pol, to czas jest
O( n*log(n)) oraz istnieje algorytm, ktory pozwala wybrac
element n/2 co do wielkosci w czasie O( n ) [ tak na prawde to pozwala
wybrac element x-ty co do wielkosci, 1<=x<=n ] ) i wtedy quicksort
ma pesymistyczna zlozonosc czasowa O(n*log(n)).

Czyli oba algorytmy moga miec taka sama pesymistyczna zlozonosc,
i dla sensownych rozmiarow danych czas moze znacznie zalezec od
implementacji.

Tak pomyslalem, ze jak sie nauczylem, to teraz moge opowiedziec :-)

Lukasz Sznuk
lsz...@zodiac1.mimuw.edu.pl

In article <311994...@laser.mimuw.edu.pl> Lukasz Sznuk <lsz...@laser.mimuw.edu.pl> writes:
>Jerzy Tarasiuk wrote:
>> z testowania, dla losowych danych quick sort byl zwykle nieco
>> wolniejszy, czasem troche szybszy, a czasem sporo wolniejszy.
>> Nie badalem dlaczego, i tak quick sort ma bardzo powazna wade -
>> mozliwosc wystapienia najgorszego przypadku, malo prawdopodobna,

>Co do heapsort to pesymistyczny czas dzialania jest O(n*log(n)),
>gdzie n to rozmiar danych. ( Czyli zawsze wykonamy <= jakas stala *
>n * log n operacji porownywania i przestwiania )
>Quicksort ma pesymistyczny czas O( n^2 ), ktory wystapi tylko przy
>bardzo zlosliwych danych. Poza tym, w quicksort mozna wprowadzic

O gorszych wynikach decyduje nie najgorszy przypadek, ktorego
prawdopodobienstwo jest 1/n!, ale wystapienie znaczacej ilosci
nieoptymalnych podzialow, co jakos calkiem czesto mi wychodzilo.

>usprawnienie ( zle jest wtedy, gdy dokonywane podzialy nie sa optymalne;
>czyli jezeli zawsze dokonywac podzialu pol na pol, to czas jest
>O( n*log(n)) oraz istnieje algorytm, ktory pozwala wybrac
>element n/2 co do wielkosci w czasie O( n ) [ tak na prawde to pozwala
>wybrac element x-ty co do wielkosci, 1<=x<=n ] ) i wtedy quicksort
>ma pesymistyczna zlozonosc czasowa O(n*log(n)).

A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie
mediany (tak sie nazywa w ksiazce Wirtha element n/2), trzeba
potem dzielic dalej, wynik jest O(n^2)... :-(

Jerzy Tarasiuk wrote:
> 
> O gorszych wynikach decyduje nie najgorszy przypadek, ktorego
> prawdopodobienstwo jest 1/n!, ale wystapienie znaczacej ilosci
> nieoptymalnych podzialow, co jakos calkiem czesto mi wychodzilo.
> 

Tu sie zgadzam... ale jezeli za kazdym razem wezmiemy mediane jako 
element wzgledem ktorwgo bedziemy dzielic, to ciag podzialow bedzie 
optymalny.

[...]
> 
> A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie
> mediany (tak sie nazywa w ksiazce Wirtha element n/2), trzeba
> potem dzielic dalej, wynik jest O(n^2)... :-(

Troche chory jestem, wiec moze zle licze, ale mi n^2 nie wychodzi...

Wezmy ciag danych wejsciowych dlugosci n. Jezeli za kazdym razem 
dokonujemy optymalnego podzialu, to bedziemy mieli log n krokow ( Wirth, 
strona 93 ). Wobec tego czas dzialania algorytmu bedzie log(n)*O(t),
gdzie t - ograniczenie gorne na czas kroku; To sprobujmy policzyc t.
Zalozmy, ze wejsciowy ciag mamy podzielony na x czesci. Wowczas dla 
kazdej czesci musimy znalezc mediane ( czas O(n/x) = O(n), bo x jest 
stale ) oraz dokonac przestawien ( znowu O(n) ). Czyli dla kazdej z x 
czesci O(n)+O(n)=O(n) operacji. Czesci jest x, x jest stale, czyli dla 
calego ciagu dlugosci n wykonujemy x*O(n) = O(n) operacji. Czyli czas 
dzialania calego algorytmu to log n*(O(n))=O(n*log(n))

Tak mi wyszlo...
Lukasz Sznuk
lsz...@zodiac1.mimuw.edu.pl

Lukasz Sznuk (lsz...@laser.mimuw.edu.pl) wrote:
: Jerzy Tarasiuk wrote:
: > O gorszych wynikach decyduje nie najgorszy przypadek, ktorego
: > prawdopodobienstwo jest 1/n!, ale wystapienie znaczacej ilosci
: > nieoptymalnych podzialow, co jakos calkiem czesto mi wychodzilo.

: Tu sie zgadzam... ale jezeli za kazdym razem wezmiemy mediane jako 
: element wzgledem ktorwgo bedziemy dzielic, to ciag podzialow bedzie 
: optymalny.

He, he -tylko znajdziesz te mediane? Najszybszy znany algorytm stosuje
technike bardzo podobna do quicksorta. ...

: [...]
: > A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie
: > mediany (tak sie nazywa w ksiazce Wirtha element n/2), trzeba
: > potem dzielic dalej, wynik jest O(n^2)... :-(
: Troche chory jestem, wiec moze zle licze, ale mi n^2 nie wychodzi...

A ile zalozyles na znalezienie mediany? I czy ten algorytm nie podlega
podebnemu problemowi co quicksort - przy zlisliwych danych dziala n^2..

Jeszcze jeden problem - ile by nie wydluzyl, heapsort jest bardzo blisko.
Jak pisalem - w praktycznych wynikach heapsort jest okolo dwa razy gorszy 
niz quicksort. policz mediane - qs bedzie wolniejszy. A czas hs jest bardzo
stabilny...


Jaroslaw Lis

+------------------------------------------------------------------------+
| l...@ict.pwr.wroc.pl         | Institute of Engineering Cybernetics     |
| tel  48-71-202636           | Technical University of Wroclaw, Poland  |
| fax  48-71-203408 or 517398 |                                          |
+------------------------------------------------------------------------+

>>>>> "L" == Lukasz Sznuk <lsz...@laser.mimuw.edu.pl> writes:
L> Jerzy Tarasiuk wrote:
L> Tu sie zgadzam... ale jezeli za kazdym razem wezmiemy mediane jako 
L> element wzgledem ktorwgo bedziemy dzielic, to ciag podzialow bedzie 
>> A nie, nie tak prosto: nie wystarczy jednokrotne znalezienie

Fakt, cos pokrecilem - rzeczywiscie jest mniej krokow, jezeli tylko
znajduje sie mediane z N elementow w N krokach. A jaki jest ten
algorytm znajdowania mediany? Czy to moze jest w ksiazce Wirtha
"Algorytmy + struktury danych = programy", czy jakiejs innej?