W
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
