Quicksort, C++, mój program

Odpowiedz Nowy wątek
2014-07-31 14:17
0

Hej. Właśnie tu napisałem Quicksort. Niestety nie działa. Męczę się ze znalezieniem błędu i nic. Jak ktoś pomoże będę wdzięczny. Jako piwot przyjąłem pierwszy element tablicy.

#include <iostream>

using namespace std;

void Test(int tab[],int pierwszy,int ostatni)
{
    int lewy=pierwszy;
    int prawy=ostatni;
    int piwot=tab[pierwszy];
    do
    {
        while(tab[lewy]<piwot)
            lewy++;
        while(tab[prawy]>piwot)
            prawy--;
        if(lewy<=prawy)
        {
            swap(tab[lewy],tab[prawy]);
            lewy++;
            prawy--;
        }
    }while(lewy<=prawy);
    swap(tab[pierwszy],tab[prawy]);
    Test(tab,pierwszy,prawy-1);
    Test(tab,prawy+1,ostatni);
}

int main()
{
    const int rozmiar=5;
    int tab[rozmiar]={7,4,2,5,1};
    Test(tab,0,rozmiar-1);
    for(int i=0;i<rozmiar;i++)
        cout << tab[i] << " ";
    return 0;
}
edytowany 1x, ostatnio: Mikilll, 2014-07-31 14:18

Pozostało 580 znaków

2014-07-31 14:23
12
0

Pokaż jak robisz swap.

Pozostało 580 znaków

2014-07-31 14:38
12
0
Test(tab,pierwszy,prawy-1);
Test(tab,prawy+1,ostatni);

Omijasz element o indeksie prawy.

Omijam, ponieważ wcześniej zrobiłem swap(tab[pierwszy],tab[prawy]). No i teraz na miejscu prawy znajduje się tab[pierwszy] czyli piwot. A piwot znajduje się na właściwym miejscu. Wg mnie gdzie indziej tkwi problem. - Mikilll 2014-07-31 15:45

Pozostało 580 znaków

2014-07-31 17:50

Według mnie, tablica po wyjściu z funkcji pozostanie niezmieniona, bo w funkcji operacje są wykonywane na wirtualnej kopii, która jest usuwana w czasie zakończenia działania funkcji, możesz użyć do tego referencji, czyli:

void Test( int& tab[], int pierwszy, int ostatni) 

.
Poza tym brakuje warunku zakończenia rekurencji tej funkcji, bo nie masz opcji, kiedy funkcja kończy się bez wywołania samej siebie.

Może przeczytaj jakieś podstawy z języka C/C++ zanim zaczniesz odpowiadać w tym dziale. - _13th_Dragon 2014-07-31 17:59
Cały czas się uczę, więc jak zarzucasz mi brak kompetencji, popraw mnie, proszę, tam gdzie się pomyliłem :) - zagura 2014-07-31 18:09
Z zakresu tablic - kompletny brak kompetencji: http://ideone.com/dqUNd1 - _13th_Dragon 2014-07-31 18:17
@zagura C++ faktycznie zwykle namiętnie wszystko kopuje - zmienne, obiekty i w ogóle, ale akurat tablice są wyjątkiem :D - Shalom 2014-07-31 18:39
Może i na temat tablic nie masz jeszcze odpowiedniej wiedzy, ale z tą rekurencją miałeś rację. Brakuje warunku zakończenia rekurencji. Dzięki za pomoc. - Mikilll 2014-07-31 19:32

Pozostało 580 znaków

2014-07-31 18:40
1

@Mikilll debuger w dłoń i klikaj. Nikt tego za ciebie nie zrobi.


Masz problem? Pisz na forum, nie do mnie. Nie masz problemów? Kup komputer...

Pozostało 580 znaków

2014-07-31 19:34
0

Dobra! Już ogarnąłem panowie. Brakowało warunku zakończenia rekurencji, a także powinno być

int lewy=pierwszy+1;

ponieważ uwzględnianie elementu pierwszego jest bez sensu, gdyż jest to piwot.

#include <iostream>

using namespace std;

void Test(int tab[],int pierwszy,int ostatni)
{
    if(pierwszy>=ostatni) return;
    int lewy=pierwszy+1;
    int prawy=ostatni;
    int piwot=tab[pierwszy];
    do
    {
        while(tab[lewy]<piwot)
            lewy++;
        while(tab[prawy]>piwot)
            prawy--;
        if(lewy<=prawy)
        {
            swap(tab[lewy],tab[prawy]);
            lewy++;
            prawy--;
        }
    }while(lewy<prawy);
    swap(tab[pierwszy],tab[prawy]);
    Test(tab,pierwszy,prawy-1);
    Test(tab,prawy+1,ostatni);
}

int main()
{
    const int rozmiar=5;
    int tab[rozmiar]={7,4,2,5,1};
    Test(tab,0,rozmiar-1);
    for(int i=0;i<rozmiar;i++)
        cout << tab[i] << " ";
    return 0;
}

Pozostało 580 znaków

2014-07-31 19:40
12
0

Prościej by było jakbyś na początku napisał co się dzieje, a nie że nie działa i już.

A co niby miałem napisać? Program się kompilował normalnie, tylko że nie dało się uruchomić bo był błąd krytyczny. A błąd ten spowodowany był nieskończoną rekurencją. - Mikilll 2014-07-31 19:48
"Nie działa" zwykle oznacza ze "daje złe wyniki" a nie "wysypuje się". - Shalom 2014-07-31 20:11
Dzięki za info. - Mikilll 2014-08-01 17:01

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0