Quick sort - algorytm

0

Partition do algorytmu Quick sort

Partition(A[l..r])
piwot<--A[l]; i<--l+1; j<--r
koniec <-- FALSE
while (not koniec)
  do while (i<r and A[i]<piwot)
       do i<--i+1
     while (j>l and A[j]>=piwot)
       do j<-- j-1
     if i<j
       then zamien A[i], A[j])
           i<--i+1
           j<--j-1
       else koniec <-- TRUE
A[l]<--A[j]
A[j]<--piwot
return j
  • 3 i 13 linijki **
  • TRUE I FALSE, to są wartości logiczne, czytałem trochę o tym w internecie, ale co robi w algorytmie?
  • jeśli i będzie większe od j to oznacza koniec ("else koniec <-- TRUE), a co robi linijka 3? Po co ona jest?
  • 4 linijka **
  • while (not koniec) - rozumiem, że oznacza "jeśli nie koniec", to wykonuj (linie 5-13)
  • 14 i 15 linijki **
  • do tego przechodzimy, gdy nie będzie się zgadzało (if i<j), tak?
    P.S. Dodam, że bardzo pomogliście mi w zrozumieniu bubble sort, dzięki temu już ogarnąłem 3 znane algorytmy sortowania: selection sort, insertion sort oraz counting sort.
1

3, 4 i 13 linijka
Ta zmienna koniec oraz while (not koniec) to tylko czytelny sposób zapisania warunku wyjścia z pętli - na początku koniec jest fałszem/nieprawdą (tzn. nie koniec). Następnie wykonujemy pętlę while do momentu kiedy nie skończyliśmy (while not koniec). Aż w momencie kiedy ktoś przypisze zmiennej koniec wartość true i pętla się więcej razy nie wykona.

14 i 15 linijki
Tak, patrz wyżej - kiedy i>=j to wykona się else, koniec dostanie True i wykona się kod za while.

Zresztą, czytanie i rozumienie pojedynczych linijek to niekoniecznie najlepszy sposób na zrozumienie algorytmu, ale może uczysz się inaczej niż ja ;]. IMO lepiej by było zrozumieć o co chodzi w QS, spróbować samemu zaimplementować podobny algorytm w dowolnym języku a dopiero później patrzeć na rozwiązanie wzorcowe czyli pseudokod.

1

@midek wydaje mi się ze kolega @msm ma racje - spróbuj zrozumieć co ten algorytm robi ;)
Partition służy do podzielenia wejściowej tablicy na dwie części:

  • mniejsze od pivota
  • większe od pivota
    U ciebie pivot jest elementem skrajnym, więc to jest tzw wersja Lomuto. Czasem pivot jest elementem środkowym i to jest wersja Hoara.
    Cały ten algorytm wygląda tak że przelatujesz po tablicy z jednej strony (od początku) i szukasz elementu który nie pasuje - czyli skoro jesteśmy teraz po "lewej" stronie to szukamy elementu który jest większy od pivota i jak znajdziemy to go zapamiętujemy. Następnie lecimy z drugiej strony tablicy (od końca) i szukamy elementu który nie pasuje - czyli jesteśmy po "prawej" i szukamy elementu mniejszego od pivota.
    Jeśli znajdziemy takie 2 elementy to zamieniamy je miejscami (czyli do miejsc do których doszliśmy mamy faktycznie w tablicy elementy mniejsze po jednej stronie i większe po drugiej). Następnie powtarzamy tą czynność aż nam sie nie "zejdą" te dwie części tablicy (czyli zejdą nam się liczniki i oraz j).
    Tak podzieloną tablicę będziemy w quicksorcie następnie znów dzielić (osobno będziemy dzielic jedną stronę i osobno drugą).
0

Panowie, bardzo dziękuję za wyjaśnienie :) Teraz już jest wszystko dla mnie jasne :) Potrafię już zilustrować przykład na podstawie tego algorytmu. Więcej pytań do tego algorytmu już nie mam.

Spróbowałem zrozumieć ten algorytm i mogę powiedzieć, że dobrze go zrozumiałem. Miałem wielkie wątpliwości co do true i false. Dobrze jest kogoś zapytać, niż być pewnym, że rozumiem ten algorytm. Mam czasami, że rozumiem wszystko, a po jakimś czasie okazuje się, że źle myślałem.

Dziękuję także za radę. Skoro to pomaga, to spróbuję po kolokwium. Czasu jest niewiele, a muszę dobrze zrozumieć algorytmy różnych sortowań i potrafić to pokazać na przykładzie.

Jeszcze raz dziękuję :)

1 użytkowników online, w tym zalogowanych: 0, gości: 1