algorytm quicksort a jego implementacja w C++

Question

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

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 

Answer 1

Chyba najlepiej wizualizuje quicksort animacja:

https://www.youtube.com/watch?v=vxENKlcs2Tw

Comments

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)...