🚀 go-pugleaf

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