Wywala program podczas rekurencji - QuickSort

Question

Cześć, potrzebuje zaimplementować QuickSorta. Oglądałem film z pewnego kanału odnośnie jak działa i była tam też również implementacja, którą po całkowitym zrozumieniu postanowiłem przekopiować.

void quick_Sort(int *tab, int left, int right)
{
    int border = right-1;
    int pivot = tab[right];
    int i = left;

    if(left>=right)
    {
        return;
    }


    while(i < right)
    {
        if(tab[i] < pivot)
        {
            border++;
            if(border != i)
            {
                swap(tab, border, i);
            }
        }
        i++;
    }

    border++;
    if(border != right)
    {
        swap(tab, border, right);
    }
    quick_Sort(tab,left,border-1);
    quick_Sort(tab,border+1,right);

    for(i=0; i<5; i++)
    {
        printf("%d  ",tab[i]);
    }
}

Niestety program wywala na końcu funkcji, gdy ma zostać wywołana rekurencja.

Wie ktoś o co chodzi?

Comments

Na pierwszy rzut oka patrząc zmienna border powinna być border=left-1;

Po za tym ten kod może być bardziej przejrzysty jeśli wsadzimy partycjonowanie Lomuto do

innej funkcji. https://www.geeksforgeeks.org/quick-sort/

---

Faktycznie!

Tylko teraz mam inny problem, aby sprawdzić czy funkcja jest posortowana, dodaje na końcu pętle for z printfem w środku, jak to jest w moim kodzie.

Wykonuje sie ona dwa razy, czyli dwa razy wypisuje mi 12345 12345.

Wiesz moze czym to jest spodowane, czy własnie tymi funkcjami rekurencyjnymi?

---

Zrób dopiero wyświetlanie całkowitym zakończeniu funkcji.To że się wyświetla 2 razy jest spowodowane rekurencja.Jeśli nie wiesz co to rekurencja nie bedzięsz czaił quicksorta ani innych algorytmów z zasadą dziel i zwyciężaj.

---

Wiem co to jest rekurencja.

W sensie chodzi Ci o to, by wywalić tę pętle gdzieś do maina aniżeli w funkcji?

---

tak, jeśli użyjemy quicksorta do posortowanej tablicy ta twoja petla odpali sie n razy ,gdzie n to wielkość tablicy

Answer 1

Z tym algorytmem jest coś bardzo nie tak. Jak wrzuciłem to w debugger to okazało się, że wywala się gdy right ma wartość 300, dla tablicy o dlugosci 11. To nie ma prawa działać.

Inkrementujesz border tak beztrosko a nigdzie nie sprawdzasz czy Ci to nie wychodzi poza dlugość tablicy.

Jak ogarne jak to naprawić to dam znać.

Answer 2

Jest ktoś w stanie rozszyfrować? Wrzucam filmik z którego to wziąłem: https://www.youtube.com/watch?v=SKmsk2Rd7oE