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

Wywala program podczas rekurencji - QuickSort

VPS Starter Arubacloud
0 głosów
256 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,820 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 588 wizyt
0 głosów
4 odpowiedzi 487 wizyt
pytanie zadane 2 listopada 2018 w C i C++ przez Maciek6997 Nowicjusz (160 p.)
0 głosów
1 odpowiedź 242 wizyt
pytanie zadane 7 czerwca 2018 w C i C++ przez kikosiak Obywatel (1,010 p.)

92,452 zapytań

141,262 odpowiedzi

319,077 komentarzy

61,854 pasjonatów

Motyw:

Akcja Pajacyk

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

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Akademia Sekuraka 2024 zapewnia dostęp do minimum 15 szkoleń online z bezpieczeństwa IT oraz dostęp także do materiałów z edycji Sekurak Academy z roku 2023!

Przy zakupie możecie skorzystać z kodu: pasja-akademia - użyjcie go w koszyku, a uzyskacie rabat -30% na bilety w wersji "Standard"! Więcej informacji na temat akademii 2024 znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...