[Algorytmika]Element osiowy w sortowaniu Quicksort

Sushi271
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 11 maja 2012, o 20:43
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: Sushi271 » 11 maja 2012, o 20:51

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.
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

Awatar użytkownika
Yaco_89
Użytkownik
Użytkownik
Posty: 992
Rejestracja: 1 kwie 2008, o 00:29
Płeć: Mężczyzna
Lokalizacja: Tychy/Kraków
Podziękował: 7 razy
Pomógł: 204 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: Yaco_89 » 11 maja 2012, o 20:59

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

Sushi271
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 11 maja 2012, o 20:43
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: Sushi271 » 11 maja 2012, o 21:19

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?

marcin_smu
Użytkownik
Użytkownik
Posty: 53
Rejestracja: 21 lut 2011, o 20:49
Płeć: Mężczyzna
Lokalizacja: Skierniewice
Pomógł: 10 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: marcin_smu » 11 maja 2012, o 22:38

[quote="Sushi271"]Policzenie mediany samo w sobie wymaga posortowania zbioru.[/quote]
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.

Sushi271
Użytkownik
Użytkownik
Posty: 8
Rejestracja: 11 maja 2012, o 20:43
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: Sushi271 » 11 maja 2012, o 23:32

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

matinf
Użytkownik
Użytkownik
Posty: 1922
Rejestracja: 26 mar 2012, o 18:52
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 695 razy
Pomógł: 4 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: matinf » 12 maja 2012, o 12:05

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

Awatar użytkownika
Yaco_89
Użytkownik
Użytkownik
Posty: 992
Rejestracja: 1 kwie 2008, o 00:29
Płeć: Mężczyzna
Lokalizacja: Tychy/Kraków
Podziękował: 7 razy
Pomógł: 204 razy

[Algorytmika]Element osiowy w sortowaniu Quicksort

Post autor: Yaco_89 » 12 maja 2012, o 12:15

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.

ODPOWIEDZ