[Eli] Quicksort
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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...
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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?
Gdzie napotykasz problem?
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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.
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.
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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.
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.
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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
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
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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
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
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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?
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?
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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...
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...
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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ść?
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ść?
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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.
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.
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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?
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Eli] Quicksort
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ę.
-
- Użytkownik
- Posty: 50
- Rejestracja: 29 lis 2011, o 16:00
- Płeć: Kobieta
- Lokalizacja: Polska
- Podziękował: 1 raz
[Eli] Quicksort
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?