• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

algorytm quicksort a jego implementacja w C++

0 głosów
110 wizyt
pytanie zadane 10 stycznia w C i C++ przez Zemynele Nowicjusz (120 p.)

Witajcie! Jestem na początku drogi jeśli chodzi o programowanie, jest to też moje pierwsze pytanie na forum, dlatego proszę o wyrozumiałość jeśli, pomimo starań, nie uda mi się zrobić wszystkiego zgodnie z regulaminem wink

Od jakiegoś czasu uczę się programowania (C++) z kursu p. Mirosława Zelenta (uwielbiam i polecam!) jednak jedna rzecz z odcinka 14 (o sortowaniu) nie daje mi spokoju. Dokładnie chodzi o założenia algorytmu quicksort a jego implementację w C++. Poniżej wklejam kod, jaki p. Mirosław podał w swoim filmiku:

void quicksort(int *tablica, int lewy, int prawy)
{
    int v=tablica[(lewy+prawy)/2];
    int i,j,x;
    i=lewy;
    j=prawy;
    do
    {
        while (tablica[i]<v) i++;
        while (tablica[j]>v) j--;
        if (i<=j)
        {
            x=tablica[i];
            tablica[i]=tablica[j];
            tablica[j]=x;
            i++; j--;
        }
    }
    while (i<=j);
    if (j>lewy) quicksort(tablica,lewy, j);
    if (i<prawy) quicksort(tablica, i, prawy);
}

I teraz tak: jeśli dobrze wszystko rozumiem, założeniem quicksortu (sortującego rosnąco) jest takie posortowanie tablicy, aby wszystkie elementy większe od osi znalazły się na prawo od osi, a mniejsze na lewo, po czym następują kolejne sortowania poprzez dalsze dzielenie powstałych "podtablic". Natomiast w podanej implementacji, jeśli dobrze widzę, powstaną raczej dwa zbiory liczb - zbiór liczb większych i mniejszych od osi, w jednym z nich znajdzie się oś, jednak niekoniecznie będzie ona "oddzielała" te dwa zbiory, np. dla tablicy: 29, 36, 2, 12, 53, 4, 70 po pierwszym sortowaniu będziemy mieć sytuację: 4 12 2 36 53 29 70, gdzie oś = 12, a więc pogrubiona przeze mnie liczba 2 leży po jej prawej stronie... Czy ktoś wie, dlaczego ta implementacja tak wygląda? Może ja coś zrozumiałam na opak? Z góry dzięki wielkie za wyjaśnienia, nie ukrywam, że temat trochę spędza mi sen z powiek cheeky

1 odpowiedź

+1 głos
odpowiedź 10 stycznia przez shead VIP (131,460 p.)
Chyba najlepiej wizualizuje quicksort animacja:

https://www.youtube.com/watch?v=vxENKlcs2Tw
komentarz 10 stycznia przez Zemynele Nowicjusz (120 p.)
dzięki, znam tę animację, bardzo fajna :) niestety nie wyjaśnia mojego problemu, który dotyczy implementacji Quicksorta wg podanego wyżej kodu, który wskazuje, że pivot (oś) jednak nie w każdym przypadku będzie znajdował się na swoim miejscu po pierwszym wywołaniu (zanim funkcja zacznie wywołania rekurencyjne)...

Podobne pytania

0 głosów
1 odpowiedź 96 wizyt
pytanie zadane 19 stycznia w JavaScript, jQuery, AJAX przez ZaXi Nowicjusz (150 p.)
0 głosów
1 odpowiedź 53 wizyt
pytanie zadane 22 sierpnia 2016 w C i C++ przez Piotr Lis Obywatel (1,140 p.)
0 głosów
3 odpowiedzi 110 wizyt
pytanie zadane 2 czerwca 2015 w C i C++ przez Criss VIP (115,800 p.)
Obowiązuje już zaktualizowany regulamin.

Czy wiesz, że nie musisz już odświeżać strony głównej?

Lista pytań i odpowiedzi aktualizuje się automatycznie!

38,636 zapytań

76,522 odpowiedzi

149,475 komentarzy

18,086 pasjonatów

Przeglądających: 228
Pasjonatów: 17 Gości: 211

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...