1 / 4
May 2023

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?

  • created

    May '23
  • last reply

    May '23
  • 3

    replies

  • 331

    views

  • 3

    users

  • 4

    likes

  • 2

    links

Czesc, kod najlepiej podawaj jako link do kompletnego, działającego programu na ideone.com2.
Jezeli chcesz bardziej sie dowiedziec, co robi dany algorytm, możesz dodać do niego tzw. debugi, czyli wypisywanie obecnego stanu, wartosci zmiennych itd.
Przyklad taki dla tego powyższego quicksorta5.
Na wyjsciu stderr są debugi, ktore pokazują co tam się dzieje.
(Nie analizowałem kodu, jedynie dodałem debugi + funkcję main, aby program był kompletny.)

Wykona się, bo i oraz j to wartości indeksów, a nie elementów tablicy. Będą one miały wartości: i=1, j=5, czyli warunek będzie spełniony.

Coo? Teraz to ma dla mnie sens. Nie wierzę, że na to nie wpadłem ale najwidoczniej skupiłem się na czym innym niż powinienem. Bardzo dziękuję za pomoc