Siemka.
Nie radze sobie z implementacją algorytmu quick sort.
Prosiłbym żeby mi to ktoś to rozpisał dość szczegółowo co jak i dlaczego.
Najlepiej w jakimś pseudokodzie
C 0
http://lmgtfy.com/?q=algorytm+quicksort i pierwszy link...
- Rejestracja:prawie 13 lat
- Ostatnio:dzień
- Postów:365
0
www.youtube.com/watch?v=ywWBy6J5gz8
Jeżeli nadal tego nie rozumiesz... może chociaż zmienisz zainteresowania na taniec ...
no dobra jeszcze masz w ramach ostatniej szansy http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0018.php
- Rejestracja:ponad 21 lat
- Ostatnio:około 17 godzin
0
Wybierasz z tablicy byle jaki element, tzw. osiowy.
Wszystkie elementy mniejsze od osiowego przesuwasz na lewo od osi.
Wszystkie elementy większe od osiowego przesuwasz na prawo od osi.
Najprościej jako oś wybrać pierwszy element, w pętli jechać po wszystkich dalszych i przesuwać przed oś wszystkie mniejsze od osi.
Teraz tablica wygląda tak:
[mniejsze od osi] [oś] [większe od osi]Następnie niezależnie sortujesz [mniejsze od osi] i [większe od osi] wg. tego samego algorytmu.
To jest bardzo naiwne podejście do qsorta. Jak zadziała, będzie czas na
ulepszenia.
- Rejestracja:prawie 20 lat
- Ostatnio:około 6 godzin
0
Ogólna koncepcja jest taka:
Mamy deklarację funkcji QuickSort(tablica, lewy, prawy):
- Wybieramy dowolny element i zapamiętujemy jego wartość.
- Skanując liniowo tablicę między indeksami lewy i prawy, przenosimy elementy tak, żeby po jednej stronie pivota były elementy od niego nie mniejsze, a po drugiej nie większe.
- Wywołujemy funkcję QuickSort dla jednej i drugiej części tablicy.
Azarien
w którą stronę będą przesuwane "niewiększe" czy "niemniejsze" nie ma znaczenia, ale zależnie od algorytmu lepiej tak dobrać, by ich fizycznie nie przesuwać tylko pomijać.
Wibowit
uprościłem ideę zachowując złożoność, w sumie i tak niepotrzebnie się produkuję, bo Google zna milion wyjaśnień QS
- Rejestracja:ponad 14 lat
- Ostatnio:prawie 10 lat
0
Na lewo dajesz mniejszych od siebie, na prawo większych. Powtórz dla wszystkich powstałych grupek i masz posortowaną tabelę
Kto wytłumaczy krócej? :D
Na lewo mniejsze, na prawo większe, i tak dalej. :-)
Ta - "Przestawiaj elementy i tak dalej..." ;)
0
Foxtrot napisał(a):
O moglibyście napisać kod z komentarzami co sie dzie w danym miejscu bo mi to niewychodzi
nie.
- Rejestracja:prawie 14 lat
- Ostatnio:7 dni
- Postów:2512
0
Foxtrot napisał(a):
O moglibyście napisać kod z komentarzami co sie dzie w danym miejscu bo mi to niewychodzi
Pokaż kod i się zanalizuje gdzie robisz błędy, a nie tylko marudzisz, że Ci nie wychodzi...
Zarejestruj się i dołącz do największej społeczności programistów w Polsce.
Otrzymaj wsparcie, dziel się wiedzą i rozwijaj swoje umiejętności z najlepszymi.