Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

StackOverflow problem kod QuickSorta

[es] :: C/C++ programiranje :: StackOverflow problem kod QuickSorta

[ Pregleda: 2407 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon StackOverflow problem kod QuickSorta11.11.2006. u 14:22 - pre 211 meseci
Radim na sortiranju sa algoritmom QuickSort i imam problema jer ako uzmem da sortira 10000 ili više brojeva program samo pukne. Ako ga kompajliram u BCB onda mi isto pukne i napiše stack overflow. Ali ako uzmem npr 1000 brojeva koje treba sortirati onda sve radi super.
 
Odgovor na temu

Buffy
Stanko Culaja
Sipovo, BiH

Član broj: 45310
Poruke: 312
*.teol.net.



Profil

icon Re: StackOverflow problem kod QuickSorta11.11.2006. u 15:55 - pre 211 meseci
linija koda vrijedi vise nego hiljadu rijeci.
PozdraV
 
Odgovor na temu

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon Re: StackOverflow problem kod QuickSorta11.11.2006. u 16:21 - pre 211 meseci
Code:
void QuickSortPOI(listPOI *pLeft, listPOI *pRight, listPOI *glava)
{
    listPOI *pStart;
    listPOI *pCurrent; 
    elementtypePOI nCopyInteger;

    if (pLeft == pRight) return;


    pStart = pLeft;
    pCurrent = pStart->next;

    while (1)
    {
        if (pStart->value < pCurrent->value)
        {
            nCopyInteger = pCurrent->value;
            pCurrent->value = pStart->value;
            pStart->value = nCopyInteger;
        }    
        
        if (pCurrent == pRight) break;

        pCurrent = pCurrent->next;
    }

    nCopyInteger = pLeft->value;
    pLeft->value = pCurrent->value;
    pCurrent->value = nCopyInteger;

    listPOI *pOldCurrent = pCurrent;

    pCurrent = PreviousL(pCurrent, glava);
    if (pCurrent != NULL)
    {
        if ((PreviousL(pLeft, glava) != pCurrent) && (pCurrent->next != pLeft))
            QuickSortPOI(pLeft, pCurrent, glava);
    }

    pCurrent = pOldCurrent;
    pCurrent = pCurrent->next;
    if (pCurrent != NULL)
    {
        if ((PreviousL(pCurrent, glava) != pRight) && (pRight->next != pCurrent))
            QuickSortPOI(pCurrent, pRight, glava);
    }
}



Eto kod funkcije koja mi sortira brojeve.
 
Odgovor na temu

Toxter
NS

Član broj: 39393
Poruke: 317
*.ADSL.neobee.net.



+6 Profil

icon Re: StackOverflow problem kod QuickSorta11.11.2006. u 19:22 - pre 211 meseci
Rekurzija ti je "pojela" stek.
Probaj da implementiras bez rekurzije.

Pozdrav!
Sad mu nije nista, ubio si ga k'o zeca...
 
Odgovor na temu

maximus_1
Max Maximus

Član broj: 46848
Poruke: 277
193.198.27.*



Profil

icon Re: StackOverflow problem kod QuickSorta12.11.2006. u 09:29 - pre 211 meseci
Ok, ali to onda ne bi više bio QuickSort. Upravo sam testirao do kojeg broja mogu ići. Gornja granica kod VC++ je oko 9100 brojeva, nakon toga se stack prepuni i program puca. Ne znam da li možda postoji neka opcija u VC++ da povećam stack.
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: StackOverflow problem kod QuickSorta12.11.2006. u 10:02 - pre 211 meseci
Hmmm, mislim da to ima veze s poljima kaj se preljeva stog, ima nekih kodova po webu al nisu baš simpatični a i piše da nisu baš učinkoviti u win32 okruženju. Mislim da bi se ovo dalo izbjeći da se koristi referenca, jer onda vrijednosti ne idu na stog, nek se barata s originalnim podacima... samo kaj je onda tu rekurzija pa to nejde... hmmmm

[Ovu poruku je menjao explorer-1 dana 12.11.2006. u 13:14 GMT+1]
 
Odgovor na temu

explorer-1

Član broj: 98573
Poruke: 102
*.adsl.net.t-com.hr.



Profil

icon Re: StackOverflow problem kod QuickSorta12.11.2006. u 14:29 - pre 211 meseci
Je neće tak. Ja sam napravil da korisnik unese broj elemenata. Pa mi ne javlja grešku kod kompiliranja - to bi trebalo u kompajleru biti ?
 
Odgovor na temu

yooyo

Član broj: 4891
Poruke: 1101
*.beotel.net.



Profil

icon Re: StackOverflow problem kod QuickSorta12.11.2006. u 16:16 - pre 211 meseci
Previse se zamota rekurzija... imas negde bug.
U svakom slucaju, kada je qsort u pitanju, sortiranje od 10000 elemenata ne bi trebalo da udje dublje od 15 koraka kakav god da je ulazni niz.
Nemam vremena da gledam code, ali mi se cini da posle prve while petlje pCurrent postaje pRight, pa posle toga pozivas rekurzivno qsort (pleft, prethodni od pCurrent) sto bi znacilo da pozivas od 1 do N-1 umesto do N/2, a drugi qsort poziv ide od pCurrent do pRight (a oni su jednaki, pa se tu nista nece desiti). U tvom slucaju dubina rekurzije je N umesto log2(N).

 
Odgovor na temu

[es] :: C/C++ programiranje :: StackOverflow problem kod QuickSorta

[ Pregleda: 2407 | Odgovora: 7 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.