[Eli] Quicksort

menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Witam. Czy mógłby mi ktoś pomóc w napisaniu quicksorta w Eli? Znalazłam kilka przykładów na internecie, próbowałam przenieść to na Eli, ale nic nie wychodzi...
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Nie znam środowiska Eli (i uważam je za skrajnie pokopany pomysł dla jakichkolwiek ludzi starszych niż gimnazjum), ale chyba umiem zdiagnozować problem: nie możesz "znaleźć w internecie i przenieść". Konieczne jest zrozumienie, jak działa quicksort: wybór elementu dzielącego, przestawienie elementów tablicy i rekursja...
Gdzie napotykasz problem?
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Nie do końca w tym jest problem. Znaleźć znalazłam kilka przykładów np .

Moim problem jest to, że nie znam żadnego języka programowania, nigdy nie miałam z tym styczności i nie wiem jak to przenieść na Eli, niby nic takiego, ale jednak mi problem stwarza.
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

No to od początku: czy wiesz, co to jest QuickSort, do czego służy i jak działa?
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Coś wiem, ale nie za dużo i nie wiem, czy to co wiem jest poprawne.. Jeśli się mylę to popraw mnie. Quicksort jest to algorytm, sortowania szybkiego, służący do sortowania jakiegoś ciągu liczb, dzieląc go na dwa, następnie sortując ciąg z lewej i prawej, i to chyba tyle co wiem
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Tak, dobrze. Tylko jeszcze istotna kwestia: quicksort musi bardzo odpowiednio podzielić ten ciąg na dwa. Wybiera sobie jakiś element X (na przykład pierwszy od lewej), po czym tak "miesza" tablicą, żeby elementy mniejsze od X znalazły się po lewej stronie tablicy, a elementy większe po prawej.
Kiedy to mu się uda, może bezpiecznie wywołać się rekurencyjnie na lewej i na prawej części. Po zakończeniu rekursji tablica będzie już gotowa.

Proponuję poszukać w Sieci bardziej drobiazgowego wyjaśnienia, z przykładem (co się będę produkował, tylu ludzi zrobiło to przede mną ).




...na przykład. Potem napisać sobie na kartce jakiś ciąg liczb i posortować go ręcznie tym algorytmem. Kiedy zrozumiesz, jak to działa, będzie bardzo łatwo przełożyć kolejno wszystkie kroki na dowolny język programowania.
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Mam na przykład taki ciąg liczb:

7 5 8 10 1 15 12 4 11 19 1

środkiem jest 15 i jak to dalej zrobić? Bo jak na lewo weźmiemy liczby mniejsze od 15, a na prawo większe to z prawej mało ich będzie
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Tak, po podziale tablica będzie wyglądała jakoś tak:

7 5 8 10 1 1 12 4 19 15

i podzieli się nierówno (lewa tablica 7 ... 4, prawa: 19 15) . Taki urok tego algorytmu
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Czyli 15 zamieniamy z ostatnią 1?
Później dzielimy prawą stronę na 2 i zamieniamy miejscami?
A lewą cześć dzielimy na dwa, środek wychodzi 1 i też z ostatnim zamieniamy miejscami?
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Uwaga na kolejność! Najpierw wybieramy element dzielący, potem mieszamy tablicą (małe na lewo, duże na prawo), a na końcu zastanawiamy się, jak ją podzielić (na ogół nierówno).

Na przykład Twoja tablica:
7 5 8 10 1 15 12 4 11 19 1
Wybieramy element dzielący, niech to będzie pierwszy od lewej (7). Mieszamy tablicą:
1 5 4 1 10 15 12 8 11 19 7
Teraz dzielimy ją na dwie (jak widać, równe nie będą):
1 5 4 1
10 15 12 8 11 19 7
I na każdej oddzielnie to samo: na lewej tablicy wybieramy np. 1, na prawej 10...
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Chyba nie za bardzo rozumiem...

7 5 8 10 1 1 12 4 11 dzielimy na pół, czyli 1 jest środkiem? Zamieniamy z 7, po lewej mają być mniejsze od 7, ale co z 8 i 10? Jak je przenieść?
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Oj, nie tak. Nic nie ma o tym, że dzielimy na pół. Dzielimy na dwie części, na ogół zupełnie nierówne. To, jakie te części będą, okazuje się - uwaga - dopiero na końcu! Zależy to od wyboru elementu dzielącego.
A ten z kolei wybieramy na ogół przypadkowo - w niektórych implementacjach jest to element ze środka tablicy, w niektórych na przykład pierwszy z lewej.

Przeczytaj linki, które podałem Tam jest też napisane, jak poprzestawiać elementy, żeby mniejsze od dzielącego były po lewej, większe po prawej.
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Ok, ok jeszcze bardziej wczytam się w to. Tylko czy później nie będzie problemu przeniesienia tego na Eli? I czy będzie to tak samo działało dla innych ciągów liczb?
Awatar użytkownika
paladin
Użytkownik
Użytkownik
Posty: 148
Rejestracja: 24 sty 2005, o 22:15
Płeć: Mężczyzna
Lokalizacja: Kraków
Pomógł: 19 razy

[Eli] Quicksort

Post autor: paladin »

Algorytm działa dla dowolnego ciągu. Z przeniesieniem nie powinno być problemu. Tak naprawdę procedurę "mieszającą" możesz przepisać wprost bez dokładnego zastanawiania się - to jest jedna pętla. Ale musisz dokładnie zrozumieć kiedy, dlaczego i na czym wywołuje się rekursję.
menrva
Użytkownik
Użytkownik
Posty: 50
Rejestracja: 29 lis 2011, o 16:00
Płeć: Kobieta
Lokalizacja: Polska
Podziękował: 1 raz

[Eli] Quicksort

Post autor: menrva »

Mógłbyś mi polecić jakąś książkę na temat takich algorytmów? Najlepiej taką, gdzie byłyby takowe schematy blokowe jak w Eli i dokładnie krok po kroku wszystko wytłumaczone?
ODPOWIEDZ