Cześć,
Uczę się programowania hobbystycznie i jak dotąd nawet jak miałem jakiś problem dawałem sobie czas i zawsze rozwiązanie wpadało mi do głowy. Teraz takim problemem jest implementacja quick sort w c++ ale nie mogę sobie z tym sam poradzić, dlatego zgłaszam się do was.
Nie potrafię zrozumieć czemu ta implementacja działa (sortuje rosnąco) i gdy rozpisuję sobie na kartce kolejne kroki to zatrzymuję się bardzo szybko. Ale po kolei, tu implementacja
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);
Weźmy taką tablicę: 12-81-49-17-29-42
Biorąc za oś 49 (tak wiem, że w tym wypadku program wybrał by 17 ale nie o to chodzi)
i to 12 j to 42
Zaczyna się pętla do. i jest mniejsze niż oś więc i to teraz 81.
j nie jest większe od osi więc j zostaje na miejscu.
if się nie wykonuje bo i nie jest mniejsze od j.
While nie jest spełniony więc pętla nie wykonuje się drugi raz.
Tylko pierwszy z dwóch ostatnich if’ów teraz się wykonuje.
Nowa tablica to 81-49-17-29-42
oś to 17 i to 81 j to 42
Pętla do się wykonuje, i zostaje na miejscu, j to teraz 29.
Dalej nic się nie wykonuje do ostatniego if’a ale wtedy tablica zostaje taka sama bo “prawy” to nadal 42 i koło się zamyka, każde kolejne wywołanie funkcji będzie dawać ten sam wynik 81-49-17-29-42.
Czego nie rozumiem? Ktoś opisał by mi co się dzieje po kolei, żebym mógł zrozumieć dokładnie zasadę działania tego algorytmu?
