Drzewo rekursji dla quicksorta

Question

Cześć,

od razu na początku powiem, że nie wiedizałem w której kategorii to umieścić, dlatego z góry przepraszam za to.

 

Potrzebuje narysowac dla quick sorta drzewo rekursji dla tablicy : 5,19,18,4,3,7,9,18,17,4

Wie ktoś jak to zrobić?

Answer 1

A pomyśl sobie jak działa quicksort - bierze wszystkie elementy, bierze środkowy (z tym zależy od algorytmu ale generalnie najprościej tak to działa) i ustawia na prawo mniejsze na lewo większe, potem robi to samo aż dojdzie do pojedynczych elementów. Więc spróbujmy to zapisać.

Na początku mamy:                                                 6,13,42,11,21,1,7,74  
                                                                                    /                         \
Po pierwszym przejściu:                                   6,7,1,11                   21,42,13,74
                                                                      /            \                       /                \
Po drugim:                                                6,1,7          11               21,13,42           74
                                                               /       \                              /        \
...                                                          1         6,7                        13        21,42
                                                                        /   \                                      /    \
                                                                       6    7                                    21    42

I potem składamy od dołu: 1, 6,7,11,12,21,42,74

Ja założyłem, że wybieramy element ze środka (jak jest parzysta liczba elementów to ten na lewo od środka) - taki niezoptymalizowany quicksort i tak to w miarę wygląda. Po prostu rozpisz sobie kolejne przejścia, tylko zwróć uwagę które elementy będą zamieniane z którymi. 
Dla swojego przykładu zrób już sam, mam nadzieję że w miarę załapałeś o co chodzi, co najwyżej to możesz wrzucić rozwiązanie swojego przykładu w komentarzu to zajrzę jak będę miał chwilę.

Comments

Ja znam takiego quicksorta, że pivot to ostatnia liczba. Załóżmy mamy liczby 4,0,2,1,3

Przed pierwszym elementem jest granica.

Jeżeli dana liczba jest mniejsza od pivota, to jest zamieniana z liczbą na prawo od granicy i granica jest przesuwana, jeżeli liczba jest większa to nic się nie dzieje i granica stoi.

Czyli by było tak:

4 jest większa od 3, więc granica stoi

| 4,0,2,1,3

0 jest mniejsze od 3, więc zamieniamy z liczbą na prawo od granicy i granice przesuwamy o jeden w prawo.

0|4,2,1,3

2 tak samo jak wyżej

0,2|4,1,3

1 tak samo jak wyżej

0,2,1|4,3

I teraz zamieniamy pivota z liczbą na prawo od granicy i wiemy, że po lewej są mniejsze, po prawej większe i robimy tak samo, aż każda liczba będzie tzw pivotem.

 

U Ciebie nie rozumiem tego, skąd od razu wiesz, ze na lewo sa mniejsze i na prawo wieksze.

---

To jest dobra wersja, ja po prostu założyłem jedną z możliwości, gdzie jak masz tablicę i przedział do posortowania od p do r, to za pivota bierzesz element o indeksie (p+r)/2 i całe to przerzucanie pominąłem (ale ono musi się odbyć i u mnie działa tak że idziesz od początku jednym wskaźnikiem, od końca drugim, jak znajdziesz element większy od pivota po lewej to zatrzymujesz lewy wskaźnik i idziesz prawym, jak znajdziesz mniejszy po prawej to zamieniasz elementy miejscami i znowu idziesz lewym), zapisując to co będzie w tablicy po kolejnych przejściach rekurencji i rozbijając to na drzewo (na lewo mniejsze od pivota i pivot, na prawo większe). Oczywiście w zależności od wyboru pivota drzewo może wyglądać troszkę inaczej i dąży się do tego żeby wybrać takiego pivota, żeby było ono jak najbardziej zbalansowane, ale to już inna kwestia.