MergeSort - Was stimmt hier nicht?



  • #include <iostream>
    
    using namespace std;
    
    void ausgabeArray(int Array[], int max);
    
    void mergeSort(int Array[], int anfang, int max);
    void merge(int Array[], int anfang, int mitte, int max);
    
    int main(){
        const int max = 10;
        int Array[max] = {8,2,1,5,7,3,2,9,6,4};
    
        ausgabeArray(Array, max);
    
        mergeSort(Array, 0, max-1);
    
        ausgabeArray(Array, max);
    
        return 0;
    }
    
    void ausgabeArray(int Array[], int max){
        for(int i = 0; i < 10; i++){
            cout << Array[i] << ", ";
        }
        cout << endl;
    }
    
    void mergeSort(int Array[], int anfang, int max){
        if(anfang < max){
            int mitte = (anfang + max) / 2;
    
            mergeSort(Array, anfang, mitte);
    
            mergeSort(Array, mitte+1, max);
    
            merge(Array, anfang, mitte, max);
        }
    
    }
    
    void merge(int Array[], int anfang,int mitte, int max){
        int *tmpArray1, *tmpArray2;
        tmpArray1 = new int[mitte];
        tmpArray2 = new int[max-mitte+1];
    
        for(int i = 0; i < mitte; i++){
            tmpArray1[i] = Array[i];
        }
        for(int i = mitte+1; i < max; i++){
            tmpArray2[i] = Array[mitte + 1 + 1];
        }
    
        int j = 0;
        int k = 0;
    
        for(int i = 0; i < max; i++){
            if(tmpArray1[j] < tmpArray2[k]){
                Array[i] = tmpArray2[k++];
            }else {
                Array[i] = tmpArray1[j++];
            }
        }
        delete [] tmpArray1;
        delete [] tmpArray2;
    }
    

    Ich weiß um besten Willen nicht was mit meinem Quellcode nicht stimmt.

    Output:
    0, 0, 0, 0, 0, 0, 0, 0, 63, 4,

    bzw. Die Zahlen sind jedes mal anders 😡

    Könntet ihr mir bitte helfen und mich von der Qual erlösen 😕



  • In solchen Fällen ist es sinvoll das Programm Schritt für Schritt in einem Debugger auszuführen und sich genau anzusehen was da passiert.

    Ich empfehle erstmal ein möglichst kleines Array zu finden, das falsch sortiert wird,
    damit du dir möglichst wenige Verarbeitungsschritte anschauen musst bis der/die
    Fehler auftreten.

    Meistens fällt es einem bei sowas sehr schnell wie Schuppen von den Augen -
    vorausgesetzt man weiss wie der Algorithmus korrekt abzulaufen hat.

    Gruss,
    Finnegan


  • Mod

    Der dickste Fehler ist erst einmal, dass du in deinen Zeilen 58-62 fröhlich um 1 hinter die Grenzen deiner Arrays zugreifst.

    Der zweitdickste Fehler ist in Zeile 52, wo du fröhlich weit hinter die Grenzen deiner Arrays zugreifst.

    Höchstwahrscheinlich gibt es noch viel mehr Fehler, aber dies sind erst einmal die Zeilen, bei denen der Debugger anschlägt.

    Bitte benutz kein new. Für das was du da tust, böte sich ein vector an.



  • Den Debugger werde ich sofort anschmeißen. Bin nur nicht so vertraut damit, sollte aber dank Internet schnell gelöst sein.

    SeppJ schrieb:

    Der dickste Fehler ist erst einmal, dass du in deinen Zeilen 58-62 fröhlich um 1 hinter die Grenzen deiner Arrays zugreifst.

    Der zweitdickste Fehler ist in Zeile 52, wo du fröhlich weit hinter die Grenzen deiner Arrays zugreifst.

    Höchstwahrscheinlich gibt es noch viel mehr Fehler, aber dies sind erst einmal die Zeilen, bei denen der Debugger anschlägt.

    Bitte benutz kein new. Für das was du da tust, böte sich ein vector an.

    Zeile 52 sollte eigentlich ein i sein keine 1.

    New nutze ich um mich mit dem Pointer vertraut zu machen. Einen weiteren Zweck verfolge ich nicht damit 🙂 Denke aber nicht das mein Sort deswegen nicht funktioniert ._.

    #include <iostream>
    
    using namespace std;
    
    void ausgabeArray(int Array[], int max);
    
    void mergeSort(int Array[], int anfang, int max);
    void merge(int Array[], int anfang, int mitte, int max);
    
    int main(){
        const int max = 10;
        int Array[max] = {8,2,1,5,7,3,2,9,6,4};
    
        ausgabeArray(Array, max);
    
        mergeSort(Array, 0, max-1);
    
        ausgabeArray(Array, max);
    
        return 0;
    }
    
    void ausgabeArray(int Array[], int max){
        for(int i = 0; i < 10; i++){
            cout << Array[i] << ", ";
        }
        cout << endl;
    }
    
    void mergeSort(int Array[], int anfang, int max){
        if(anfang < max){
            int mitte = (anfang + max) / 2;
    
            mergeSort(Array, anfang, mitte);
    
            mergeSort(Array, mitte+1, max);
    
            merge(Array, anfang, mitte, max);
        }
    
    }
    
    void merge(int Array[], int anfang,int mitte, int max){
        int *tmpArray1;
        int *tmpArray2;
        tmpArray1 = new int[mitte];
        tmpArray2 = new int[mitte+1];
    
        for(int i = 0; i < mitte; i++){
            tmpArray1[i] = Array[i];
        }
        for(int i = mitte+1; i < max; i++){
            tmpArray2[i] = Array[mitte + i + 1];
        }
    
        int j = 0;
        int k = 0;
    
        for(int i = 0; i < max-1; i++){
            if(tmpArray1[j] < tmpArray2[k]){
                Array[i] = tmpArray2[k++];
            }else {
                Array[i] = tmpArray1[j++];
            }
        }
        delete [] tmpArray1;
        delete [] tmpArray2;
    }
    

    Output:

    8, 2, 0, 5, 0, 0, 0, 0, 6, 4,


  • Mod

    Das wesentliche Problem mit Zeile 53 (vormals 52) besteht nach wie vor: Welchen Wert hat i? Wo werden deine Daten hingeschrieben? Und welchen Wertebereich hat der Ausdruck mitte + i + 1 ? Arrays haben Indizes die von 0 anfangen und bis zu ihrer Größe minus 1 gehen.



  • SeppJ schrieb:

    Das wesentliche Problem mit Zeile 53 (vormals 52) besteht nach wie vor: Welchen Wert hat i? Wo werden deine Daten hingeschrieben? Und welchen Wertebereich hat der Ausdruck mitte + i + 1 ? Arrays haben Indizes die von 0 anfangen und bis zu ihrer Größe minus 1 gehen.

    oh 😮 Naturlich... Habe überall hingeschaut nur nicht dahin .. i sollte natürlich 0. Der Rest stimmt so.

    *edit
    Mit Zeile 52 möchte ich die Rechte Hälfte meines Arrays auf einen tmp kopieren. Dafür würden Array[mitte + i] die Daten notwendig sein. +1 wären in dieser Situation tatsächlich nicht notwendig... ➡

    #include <iostream>
    
    using namespace std;
    
    void ausgabeArray(int Array[], int max);
    
    void mergeSort(int Array[], int anfang, int max);
    void merge(int Array[], int anfang, int mitte, int max);
    
    int main(){
        const int max = 10;
        int Array[max] = {8,2,1,5,7,3,2,9,6,4};
    
        ausgabeArray(Array, max);
    
        mergeSort(Array, 0, max-1);
    
        ausgabeArray(Array, max);
    
        return 0;
    }
    
    void ausgabeArray(int Array[], int max){
        for(int i = 0; i < 10; i++){
            cout << Array[i] << ", ";
        }
        cout << endl;
    }
    
    void mergeSort(int Array[], int anfang, int max){
        if(anfang < max){
            int mitte = (anfang + max) / 2;
    
            mergeSort(Array, anfang, mitte);
    
            mergeSort(Array, mitte+1, max);
    
            merge(Array, anfang, mitte, max);
        }
    
    }
    
    void merge(int Array[], int anfang,int mitte, int max){
        int *tmpArray1;
        int *tmpArray2;
    
        tmpArray1 = new int[mitte];
        tmpArray2 = new int[mitte];
    
        for(int i = 0; i < mitte; i++){
            tmpArray1[i] = Array[i];
        }
        for(int i = 0; i < max - 1; i++){
            tmpArray2[i] = Array[mitte + i];
        }
    
        int j = 0;
        int k = 0;
    
        for(int i = 0; i < max-1; i++){
            if(tmpArray1[j] < tmpArray2[k]){
                Array[i] = tmpArray2[k++];
            }else {
                Array[i] = tmpArray1[j++];
            }
        }
        delete [] tmpArray1;
        delete [] tmpArray2;
    }
    

  • Mod

    Jetzt musst du aber noch aufpassen, wie viele Daten du kopierst. max-2 Elemente sind ungefähr doppelt so viel, wie du möchtest.

    Weiterhin ist nicht unbedingt klar, dass eine gerade Anzahl von Elementen sortiert werden soll. Wenn man an der Mitte teilt, kann es sein, dass eine der Hälften um 1 Element größer ist.



  • SeppJ schrieb:

    Jetzt musst du aber noch aufpassen, wie viele Daten du kopierst. max-2 Elemente sind ungefähr doppelt so viel, wie du möchtest.

    Weiterhin ist nicht unbedingt klar, dass eine gerade Anzahl von Elementen sortiert werden soll. Wenn man an der Mitte teilt, kann es sein, dass eine der Hälften um 1 Element größer ist.

    Tut mir leid 😕 Ich weiß nicht welche 2 Elemente du meinst. Ich bin mit dem Debugger drüber und habe mitgezählt wie oft die Schleife ausgeführt wird (zum kopieren) und es passt eigentlich so wie es ist.


  • Mod

    Nicht 2, sondern (max-2).


Anmelden zum Antworten