Heap Sort hilfe :(

Cabooze

Hallo allerseits,

Rekursion bereitet mir oft noch ziemliche Probleme. Mein Heapsort bricht mit run failed ab und ich weiß nicht wieso.

int n = 10;
int heapsize;

void heapify(int A[], int i){

    int tmp, max;

    if(i==0){
        l = 1;
        r = 2;
    } else {
        l = 2 * i;
        r = 2 * i + 1;
    }

    if(l <= heapsize && A[l] > A[i])
        max = l;
    else if(l <= heapsize && A[l] < A[i])
        max = i;

    if(r <= heapsize && A[r] > A[i])
        max = r;

    if(max != i){
        tmp = A[i];
        A[i] = A[max];
        A[max] = tmp;
        heapify(A,max);  //Fehlermeldung
    }

}

void buildheap(int A[]){
    for(int i = n/2; i>=0; i--){
        heapify(A,i);
    }
}

void heapsort(int A[]){
    int tmp;
    heapsize = n;
    buildheap(A);
    for(int i = n-1 ; i>=1; i--){
        tmp = A[0];
        A[0] = A[i];
        A[i] = tmp;
        heapsize--;
        heapify(A,0);
    }
}

int main(int argc, char** argv) {

    int B[10]={6,5,74,2,19,1,7,88,64,22};

    heapsort(B);

    return 0;
}

Der Fehler kommt scheinbar durch den selbstaufruf von Heapify. Wenn ich den auskommentiere kommt keine Fehlermeldung mehr. Aber ich kann mir nicht erklären woran es liegt

Cabooze

Ncoh seltsamer ist, dass ich gerade gar nichts verändert habe, und es nun seit neustem trotzdem mit run failed abbricht, auch wenn das heapify(A, max) auskommentiert bleibt. Das war eben noch nicht so. Jetzt versteh ich gar nichts mehr

tkausl

Wo kommt denn das 'n' in heapsort her?

Cabooze

Globale variable. Habs grad noch hingeschrieben

Cabooze

Also wenn ich in Zeile 31 das max rausnehme und z.B eine 1 reinschreibe kompiliert es. Nur funktioniert dann leider der Algorithmus selbst nicht... weiß nicht was ich da sonst machen soll.

Und du hältst es nicht für nötig, die Fehlermeldung des Compilers zu nennen?

Cabooze

Würde ich gerne wenn eine käme...
Er bricht mit "run failed" das kompilieren ab, wie ich sagte. Mehr bekomme ich leider auch nicht

Cabooze schrieb:

Würde ich gerne wenn eine käme...
Er bricht mit "run failed" das kompilieren ab, wie ich sagte. Mehr bekomme ich leider auch nicht

Tja, dann solltest du mal die Bedienung deiner IDE lernen. Der Compiler ist ganz sicher nicht so schweigsam.

Skym0sh0

manni66 schrieb:

Cabooze schrieb:

Würde ich gerne wenn eine käme...
Er bricht mit "run failed" das kompilieren ab, wie ich sagte. Mehr bekomme ich leider auch nicht

Tja, dann solltest du mal die Bedienung deiner IDE lernen. Der Compiler ist ganz sicher nicht so schweigsam.

Oder wenigstens den Compiler nennen...

Nathan

Warte, gibts einen Compilerfehler oder crasht das Programm?
Letzteres könnte mit deinen Arraygrenzen zu tun haben. Wenn das Array 10 groß ist, ist das letzte Element 9, nicht 10, <= ist also falsch.
Deine Nutzung von globalen Variablen ist auch nicht gerade toll...

Nathan schrieb:

Warte, gibts einen Compilerfehler oder crasht das Programm

Der Code von oben gibt bestimmt einen Compilerfehler, nämlich "undeclared variable(s) line 10+11"..

Werner Salomon

Cabooze schrieb:

Rekursion bereitet mir oft noch ziemliche Probleme. ...

an der Rekursion liegt es nicht. Es sind ein paar andere Fehler drin. Anbei die Korrektur:

// int n = 10;  // <== verzichte ganz auf globale Variablen (nur fehleranfällig)
// int heapsize;

// 'swap' braucht man öfter, daher auslagern; Alternative wäre: std::swap aus #include <algorithm>
void swap( int& a, int& b ) {
    int tmp = a;
    a = b;
    b = tmp;
}

void heapify(int A[], int heapsize, int i) { // nimm 'heapsize' mit in die Parameterliste auf!
    int l = 2 * i + 1;  // 1.) '+1' vergessen; 2.) if(i==0){ <== Fallunterscheidung ist überflüssig 
    int r = l + 1;

    int max = i;    // initiale Belegung vergessen
    if(l < heapsize && A[l] > A[i])    // '< size' statt '<= size'
        max = l;
    // else if(l <= heapsize && A[l] < A[i]) // überflüssig und fehlerhaft, da im Fall 'A[l] == A[i]'  max nicht initialisiert wurde
    //    max = i;
    if(r < heapsize && A[r] > A[max])  // 1.) '< size' statt '<= size'; 2.) statt 'A[r] > A[i]', damit der größte(!) Wert nach oben kommt
        max = r;

    if(max != i){
        swap( A[i], A[max] );
        heapify(A,heapsize,max);
    }   
}

void buildheap(int A[], int heapsize){
    for(int i = heapsize/2-1; i>=0; i--){
        heapify(A,heapsize,i);
    }
}

void heapsort(int A[], int heapsize){
    buildheap(A,heapsize);

    for( ; --heapsize > 0; ){
        swap( A[0], A[heapsize] );
        heapify(A,heapsize,0);
    }
}

int main(int /*argc*/, char** /*argv*/) {
    int B[]={6,5,74,2,19,1,7,88,64,22}; // die '10' war redundant zur Anzahl der Zahlen in der Liste
    heapsort(B, sizeof(B)/sizeof(*B));
    return 0;
}

Gruß
Werner