Matematyka.pl

Witam.

Zaintrygował mnie pewien dylemat, który nie do końca wiem jak rozstrzygnąć. Mianowicie istnieje taki bardzo popularny algorytm sortowania - Quicksort. W dużym skrócie polega on na tym, że jeżeli mamy daną nieposortowaną tablicę elementów, dzielimy ją na dwie części wg. pewnego tzw. elementu osiowego, a następnie zastosowujemy (rekurencyjnie) Quicksort osobno do lewej i prawej części. Z tego co udało mi się wyczytać, elementem osiowym może być dowolny element od najbardziej lewego, do najbardziej prawego elementu tablicy (lub części tej tablicy). Zastanawia mnie jak to wpływa na szybkość tego algorytmu? Czy nie rozsądniej byłoby brać np. zawsze w połowie? Czy gdyby się trafiła seria wybranych skrajnych elementów osiowych (np. zawsze kolejne elementy: pierwszy, sortując na prawo od niego znów pierwszy, sortując na prawo od niego znów pierwszy... itd.) nie byłoby wolniej? Nigdzie nic nie jest napisane na ten temat, a sam nie wiem jak to sprawdzić/policzyć. Zatem naprawdę mnie to intryguje.

Oczywiście że to ma wpływ i to jest wbrew pozorom dobrze opisane w literturze, w tej chwili nie podam Ci tytułów bo uczyłem się tego dosyć dawno ale z uwagi na popularność Quicksorta były robione dokładne analizy. Z tego co wiem to w praktyce spotyka się takie podejście że losuje się element osiowy, albo np. bierze pierwszy ostatni i ze środka i z tych trzech wybiera medianę. To jest bardzo istotne, bo dowodzi się że w skrajnym przypadku (jeśli w każdej iteracji wybieramy "najgorszy" element) szybkość algorytmu może być gorsza niż np. sortowania przez scalanie czy kopcowego, natomiast przeciętna szybkość (przy założeniu że tablica jest losowo pomieszana) jest bardzo dobra.

Jestem prawie pewien że będzie coś na ten temat np. w książce Cormena

O. To ciekawe. Możliwe że mediana z większej liczby elementów byłaby skuteczniejsza? Chociaż z drugiej strony policzenie mediany samo w sobie wymaga posortowania zbioru. Dla trzech elementów wystarczy znaleźć ten nie-maksymalny i nie-minimalny.

Co do Cormena... słyszeć słyszałem, ale i tak trzeba go najpierw mieć. A nielegalnego ebooka się nie tykam.

Edit:
O albo np. mediana z losowego na lewo od środkowego, środkowego i losowego na prawo od środkowego?

Sushi271 pisze:Policzenie mediany samo w sobie wymaga posortowania zbioru.

Mylisz się, medianę podobnie jak każdy inny k-ty co do wielkości element da się policzyć nawet w czasie liniowym. Aby było to czas oczekiwany robimy to podobnie do samego Quicksort'a, tylko rekurencją schodzimy jedynie w tę stronę, w której znajduje się szukany element. Da się to poprawić, aby nawet w pesymistycznym przypadku był to czas liniowy, algorytmem magicznych piątek.

O żesz. Poczytałem. Pokręcony trochę ten algorytm, ale naprawdę dobry. Ciężko uwierzyć że ma liniową złożoność! Będę musiał dorwać tego Cormena, to musi być ciekawa lektura

Qsort nie ma liniowej złożoności tylko liniowo-logarytmiczną

Myslę że marcin_smu miał na myśli złożoność algorytmu wyznaczania mediany (lub dowolnej innej stat. pozycyjnej). Do autora tematu: Cormena powinien mieć każdy szanujący się wydział matematyki/informatyki w bibliotece, natomiast uprzedzam, że przy lekturze fragemntów dotyczących "przeciętnej" analizy Quicksorta (czy jakiegokolwiek innego algorytmu z elementami losowości) konieczna może być znajomość paru rzeczy z kombinatoryki i prawdopodobieństwa ogólnie.