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).


Log in to reply