• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

Wywala program podczas rekurencji - QuickSort

0 głosów
175 wizyt
pytanie zadane 30 maja 2018 w C i C++ przez must Bywalec (2,980 p.)

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?

komentarz 31 maja 2018 przez Wunsz Użytkownik (680 p.)
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/
komentarz 31 maja 2018 przez must Bywalec (2,980 p.)
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?
1
komentarz 31 maja 2018 przez Wunsz Użytkownik (680 p.)
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.
komentarz 31 maja 2018 przez must Bywalec (2,980 p.)
Wiem co to jest rekurencja.

W sensie chodzi Ci o to, by wywalić tę pętle gdzieś do maina aniżeli w funkcji?
2
komentarz 31 maja 2018 przez Wunsz Użytkownik (680 p.)
tak, jeśli użyjemy quicksorta do posortowanej tablicy ta twoja petla odpali sie n razy ,gdzie n to wielkość tablicy

2 odpowiedzi

+1 głos
odpowiedź 1 czerwca 2018 przez RafalS VIP (122,860 p.)
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ć.
0 głosów
odpowiedź 31 maja 2018 przez must Bywalec (2,980 p.)
Jest ktoś w stanie rozszyfrować? Wrzucam filmik z którego to wziąłem: https://www.youtube.com/watch?v=SKmsk2Rd7oE

Podobne pytania

0 głosów
2 odpowiedzi 443 wizyt
0 głosów
4 odpowiedzi 269 wizyt
pytanie zadane 2 listopada 2018 w C i C++ przez Maciek6997 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 116 wizyt
pytanie zadane 7 czerwca 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)

86,526 zapytań

135,279 odpowiedzi

300,596 komentarzy

57,276 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto dwie polecane książki warte uwagi. Pełną listę znajdziesz tutaj.

...