Elirt peldaprogram...

C/C++

Hi!
A K&R C konyvbol tanulok programozgatni. 124. oldalon tartok eppen egy erdekesebb temanal es azt vettem eszre, hogy a peldaprogramban el van irva egy resz es az a baj, hogy amig nem ertem a mukodeset, addig nem is tudom kijavitani. Viszont ameddig nincs kijavitva, addig nem fogom megerteni a mukodeset. Ordogi kor... :)
A Hiba a qsort fuggvenyben van, ahol eloszor hivja a swap fuggvenyt 4 paramterrel, holott az 3-at var. Akinek megvan a konyv az esetleg utananezhetne, hogy is van ez. :\
Elore is koszi!

  • 1173 megtekintés

( uid_1526 | 2006. 06. 07., sze – 21:13 )

Szerintem a 3. paraméter (jobb) nem kell neki.

( vik1984 | 2006. 06. 07., sze – 22:01 )

Itt van egy altalanos algoritmus es a teljes koncepcio le van irva.

De ha bemasolod a kerdeses reszt, akkor sztem ki tudom javitani.

"No boom today. Boom tomorrow. There's always a boom tomorrow. What? Look, somebody's got to have some damn perspective around here. Boom, sooner or later. BOOM!" -- Lt. Cmd. Ivanova

( szaszg | 2006. 06. 07., sze – 22:29 )

Ha erre gondolsz: 


/* qsort: sort v[left]...v[right] into increasing order */
void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);
    if (left >= right) /* do nothing if array contains */
        return;        /* fewer than two elements */
    swap(v, left, (left + right)/2); /* move partition elem */
    last = left;                     /* to v[0] */
    for (i = left + 1; i <= right; i++) /* partition */
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);            /* restore partition elem */
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

akkor az angolban igy nez ki... Itt harom parameter van...

Zsiraf

Bar nem pontosan a topichoz tartozik, de errol pont tegnap olvastam a Java-s binarySearch() kapcsan, viszont mivel ez is hasonlo, erre is vonatkozik (pont a kerdeses sorra): a szamitast 

(left+right)/2

alakban vegezzuk, ezert elofordulhat, hogy a (left+right) osszeg tul nagy int-et eredmenyez, ami miatt az ertek atfordul negativba, ez pedig nem vart mukodest eredmenyezhet. Ehelyett javasolnak tobbfele modot, pl. 

left+(right-left)/2

vagy 

((unsigned) left+right) >> 1

Ez ugyan csak nagyon nagy tombok eseten okozhat gondot, de volt mar ra pelda, nem art a problemaval tisztaban lenni.
A Java-s valtozat eseteben tobb info: http://www.theserverside.com/blogs/thread.tss?thread_id=40777

Akkor bírna túlcsordulni, ha az összes elem száma 32 bites int esetén 2^30-nál nagyobb (feltételezve, hogy kezdetben bal=0). Ilyen szélsőséges esetben, mivel már amúgy is igen közel vagyunk a tömb méreténél is az int32 értékkészletének végéhez, én inkább szimplán nagyobb szélességű int-et (pl 64 biteset) használnék bűvészkedés helyett. Persze mindez csak elméleti, mert valószínűleg senki sem fog mostanában ekkora elemszámú tömböt rendezni.