> >> quicksort dzieli 'logarytmicznie' tak ze nawet poziomow
> >> zaglebien w wywolaniach na stosie nie jest tak duzo: log2(N)
> >>
> >>
> > tzn 'srednio' fakt zapomnialem o niewygodnych przypadkach
> >
> Nie pamiętam już dokładnie - to było 3 lata temu, ale implementacja oidp
> miała być "podręcznikowa z rekurencją" a ta wersja używa n dodatkowego
> miejsca. W takiej sytuacji można użyć mergesort, który jest równie
> złożony pamięciowo a stabilny i dobrze się zrównolegla. Dla porównania
> heapsort, którego bardzo lubię, działa w miejscu.
jak sie zastanowic quicksort nie jest
wcale taki dobry i defakto mozna by
przynajmniej poprobowac z liniowym
sortem na histogramie) - dla 10 tys log2 jest
13 (czyli jest to x13 wolniej) do tego jest
to dla rownomiernych podzialow a nie
wiem jak w przypadkach realnych wypaczen
moze jest jeszcze ze 2x wolniej) czyli
x20 powiedzmy - w liniowym trzebaby
pozaokraglac wspolrzedne i ograniczyc
przedzial np do 50 tys jest tez problem
ze skladowaniem zderzonych w histogramie
indeksow jako list no i pozniej z przeleceniem
histogramu ale powinno byc kilka razy
szybciej - choc problem z tym zawezonym
polem - moze metoda kombinowana sektory
i histogramsort


--
Wysłano z serwisu OnetNiusy: http://niusy.onet.pl