MergeSort Stackoverflow

[Kingh_Gilgamesh]

Hey Leute,
bin neu im Forum und auch neu im Bereich Programmieren. Ich versuche momentan einen mergeSort Algorithmus zu implementieren. Leider kommt es bei mir zu einem Stackoverflow und ich verstehe leider nicht warum. Laut Eclipse kommt es in Zeile 13 zum overflow. Des weiteren könnte ich einen Tip gebrauchen bezüglich des Ausgebens der restlichen Elemente in der linken und rechten Teilliste nachdem man durch das ganze Array iteriert ist.
Ich bedanke mich im Voraus für eure Hilfe!

 

[DrZoidberg]

Das liegt wahrscheinlich daran, dass Zeile 12 einen Fehler enthält.

 

[Kingh_Gilgamesh]

eh ja da ist wirklich ein fehler sry. aber wenn ich den korrigiere, also wenn ich (left + right)/2 nehme bekomme ich indexoutofbound in zeile 14 und 15. ne idee woran das liegen könnte?

 

[Meniskusschaden]

bekomme ich indexoutofbound in zeile 14 und 15.

Das kann nicht sein, denn in den beiden Zeilen erfolgt überhaupt kein indexbasierter Zugriff. Wahrscheinlich wird der Fehler in einer anderen Zeile ausgelöst. Stelle doch mal die komplette Fehlermeldung und dein Programm in Code-Tags hier rein (z.B. über den Button Einfügen->Code->Java). Screenshots sind für Quellcode nicht zweckmäßig.

 

[Xyz1]

// Eigentliche Arbeit ist merge

Das stimmt. Dennoch ist es ein ziemliches Fummeln mit den Indices. Ich habe das mal halbwegs noch verständlich aufgeschrieben. Was man im Inet findet, ist aber zumindest bei merge etwas anders:

        for (int j = 0; j <= 12; j++) {
            int[] a = new Random(0).ints(j, 0, 2).toArray();
            div(a, 0, a.length - 1);
            System.out.println(Arrays.toString(a));
        }

        for (int j = 0; j <= 12; j++) {
            int[] a = new Random(0).ints(j, 0, 20).toArray();
            div(a, 0, a.length - 1);
            System.out.println(Arrays.toString(a));
        }
    }

    static void div(int[] a, int l, int r) {
        int m = (r - l) / 2 + l + 1;
        if (l + 1 < r) {
            div(a, l, m - 1);
            div(a, m, r);
        }
        con(a, l, m, r);
    }

    static void con(int[] a, int l, int m, int r) {
        int len = r - l + 1;
        int[] b = new int[len];
        int ll = l;
        int mm = m;
        for (int j = 0; j < len; j++) {
            if (ll == m || mm <= r && a[ll] > a[mm]) {
                b[j] = a[mm];
                mm++;
            } else {
                b[j] = a[ll];
                ll++;
            }
        }
        for (int j = 0; j < len; j++) {
            a[l + j] = b[j];
        }
    }

[]
[1]
[1, 1]
[0, 1, 1]
[0, 1, 1, 1]
[0, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1]
[0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1]
[]
[0]
[0, 8]
[0, 8, 9]
[0, 7, 8, 9]
[0, 7, 8, 9, 15]
[0, 7, 8, 9, 13, 15]
[0, 7, 8, 9, 11, 13, 15]
[0, 1, 7, 8, 9, 11, 13, 15]
[0, 1, 7, 8, 9, 11, 13, 15, 19]
[0, 1, 7, 8, 9, 11, 13, 14, 15, 19]
[0, 1, 7, 8, 9, 11, 13, 14, 15, 17, 19]
[0, 1, 7, 8, 9, 11, 13, 14, 15, 17, 17, 19]

Viel Fun damit...

ll steht für Links temporär,
mm steht für Rechts temporär,
j ist eine Laufvariable (i hatte ich schon woanders),
div steht für divide,
con steht für conquer,
der Rest erklärt sich.......

 

[Xyz1]

Mir ist noch eingefallen, statt "ganz oft" int[] b = new int[len]; könnte man auch einmal ein großes Array definieren. Das müsste dann aber außerhalb der Methode, ginge nicht innerhalb der Methode. Und wie man es dreht es bleibt beim Speicherverhalten von (2*n), d. h.: ebenfalls IN-PLACE! AUßERDEM ist euch sicher aufgefallen: a[ll] > a[mm], d. h.: STABIL (wenn es z. B. Objekte sind).

In Java ist es sicherlich so ähnlich geschrieben. Wenn ich Zeit habe, kann ich da nachgucken, wenn gewollt. 😕