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