🚀 go-pugleaf

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)... :-(