Sortieralgorithmus- Heapsort

Kira*amp*Paddy

Hallo
Ich habe probiert den Sortieralgorithmus Heapsort zu Programmieren, doch es klappt nicht wirklich
Ich arbeite mit "Dev C++" und er zeigt mir beim Kompilieren keine Fehler an. Wenn ich das Programm jedoch ausführen möchte, bricht es mittendrinne ab. Hat vielleicht einer eine Idee was der Fehler bei meinem Quellcode sein könnte?
Ich habe meinen Quellcode angehängt und auch makiert wo er ungefähr immer abricht, vor dem Aufruf der Funktionsdefinition.
DANKE schon mal
lg Kira&Paddy

no_code

du solltest der function schon initialisierte werte übergenen... aber das noch dein kleinstes problem. dein ganzer algo ist müll wenn ich das mit kurz überlesen mal so dahinstellen darf. hier hast ein fertiges beispiel lese und lerne...

wobei das beispiel sicher auch nicht die bombe ist aber naja iwo wirst schon ein schönes snippet finden :p

Das ist schon falsch

//Eingabe
    for (int Zahl=1; Zahl<=5; Zahl++)

Indexe starten bei 0 und enden entsprechend auch bei (groesse - 1).

Kira*amp*Paddy

Ich hab das so in der Schule gelernt -.-
Könnte mir, bitte einer erklären wie das überhaupt geht?
Das Prinzip mit dem Binären Baum und blabla hab ich verstanden aber ich versteh nicht wirklich, wie man den Heapsort Programmiert. Gibt es da bestimmte richtlinien oder bestimmte Formeln an die man sich halten muss?
Im Internet sind viele Quellcodes mit Zeigern, ich möchte aber lieber mit Array machen, da ich dies so gelernt habe. Hier mal ein Quellcode auf dem World Wide Web:

#include "myheap.hpp"
#include <stdlib.h>
#include <stdio.h>

myheap::myheap(int size){
    data = new int[size + 2];
    pointer = 0;
}

myheap::myheap(int *a, int size){
    data = new int[size + 2];
    for (int i = 0; i < size; i++){
        data[i+1] = a[i];
    }
    pointer = size;
    reheap_all();
}

myheap::~myheap(){
    delete[] data;
}

void myheap::push(int item){
    pointer ++;
    data[pointer] = item;
    reheap_up(pointer);
}

void myheap::reheap_up(int start){
    int p =start;
    int new_p = p / 2;
    while (p > 1 && data[new_p] > data[p]){
        /* swap the two elements */
        int tmp = data[new_p];
        data[new_p] = data[p];
        data[p] = tmp;
        p = p / 2;
        new_p = new_p / 2;
    }
}

void myheap::reheap_all(){
    int p;
    for (p = 1; p <= pointer; p++){
        reheap_up(p);
    }
}

void myheap::reheap_down(int pointer){
    int new_p;
    if (2 * pointer > this->pointer){
        return;
    }
    if (2 * pointer + 1 <= this->pointer
            && data[2*pointer+1] < data[2*pointer]){
        new_p = 2 * pointer + 1;
    } else {
        new_p = 2 * pointer;
    }
    if (data[pointer] > data[new_p]){
        int tmp = data[pointer];
        data[pointer] = data[new_p];
        data[new_p] = tmp;
        reheap_down(new_p);
    }
}

int myheap::pop(void){
    int res = data[1];
    data[1] = data[pointer];
    pointer--;
    reheap_down(1);
    return res;
}

void myheap::check_heap_condition(void){
    int i;
    for (i = 2; i <= pointer; i++){
        if (data[i/2] > data[i]){
            printf("\nError at index %d, %d\n", i, i/2);
            exit(1);
        }

    }

}

den hab ich von der seite http://perlgeek.de/de/artikel/heap-und-heapsort

Wenn ich den Quellcode kopiere um ihn in mein "Dev-C++" einzufügen, kommen richtig viele fehler beim kompilieren. Ist das überhaupt C++? void kenn ich nur, wenn man Module macht. und was bedeutet "printf"?? Ich hab keine Ahnung

Ränkeschmied

Der von dir gepostete Code scheint beides zu sein.
In C benutzt man printf() anstelle von std::cout.
Auch wird dort bei der Deklaration einer Funktion mit leerer Parameterliste void benutzt. Was void als Rückgabewert bedeutet sollte klar sein.
Da allerdings Methoden definiert werden, ist es kein reines C sondern C/C++ Mischmasch.
Zu den Fehlern: Keine Ahnung, zum ausprobieren zeigst du zu wenig. Mindestens die Fehlermeldungen musst du schon posten.
Angemerkt sei noch, dass Dev C++ veraltet ist, und ich(und nicht nur ich) dir rate, einen anderen, aktuelleren Compiler zu benutzen.

drakon

Kira&Paddy schrieb:

Ich hab das so in der Schule gelernt -.-
Könnte mir, bitte einer erklären wie das überhaupt geht?
Das Prinzip mit dem Binären Baum und blabla hab ich verstanden aber ich versteh nicht wirklich, wie man den Heapsort Programmiert. Gibt es da bestimmte richtlinien oder bestimmte Formeln an die man sich halten muss?

Am besten ist es, wenn du mal von Hand ein Array mit Heaposrt sortierst. Das ist ganz einfach.
Zuerst musst du aus dem Array einen Heap bauen. Das ist von Hand ganz einfach und in der Programmierung benötigt das ein wenig Indexgeschubse, was ein wenig ärgerlich werden kann.
Aber von Hand baust du einfach schön linear einen binären Baum (im Moment noch ohne jegliche gute Eingenschaft) auf. Das erste Element ist das Wurzelelement, das zweite Element ist das linke Kind der Wurzel, das dritte das rechte Kind der Wurzel usw.

Also aus:

5 6 7 1 2 9

wird:

5
       6    7
      1 2  9

Dann musst du jedes Element im Baum versickern. Und das machst du von unten nach oben. Also zuerst die 9, dann die 2, dann die 1 usw.
Versickern heisst, dass du das Element, dass du versickern musst so lange mit mit dem kleisten Kind (ich gehe von einem Minheap aus) tauscht bis es kleiner ist, als die beiden Kinder.
Im obigen Baum wird daraus:

1
       2    7
      6 5  9

Und daraus kannst du dann einen korrekten Heap in Array Form bauen:

1 2 7 6 5 9

Also einfach Rückwärts das machen, was du für das erstellen des Baumes gemacht hast.

Und um jetzt eine Sortierung zu bekommen nimmst du ganz einfach das oberste Element (das kleinste) und entfernst es. An dessen Stelle stellst du das letzte Element (hier also die 9) und versickerst die 9 analog wie wir das vorher gemacht haben. Dann hast du das hier:

2
       5    7
      6 9  

sortiert: 1

Und dann wiederholst du das so lange bis das Array leer ist.

Wie gesgat die Implementierung des Arrays ist ein wenig mühsamer, weil du die Positionen des linken und rechten Kindes im Array finden musst. Das ist allerdings:

sei i die Position des Elternknotes:
Index linkes Kind: i*2 + 1
Index rechtes Kind: i*2 + 2

Dabei musst du einfach schauen, dass du nicht ausserhalb des Array zugreifst.

Ich hoffe das Vorgehen ist klar. Sonst frag einfach nochmal nach.