Hallo liebe Community,
ich arbeite gerade an einer Aufgabe in der ich den normalen MergeSort Algorithmus abändern soll. Im normalen MergeSort Algorithmus nimmt man ja ein Array und unterteilt das dann in zwei Teilarrays, diese zwei Teilarrays unterteilt man dann ja jeweils wieder in zwei Teilarrays bis man sozusagen nur Arrays mit einer Zahl drin hat.
Ich soll jetzt solch einen MergeSort Algorithmus implementieren aber so, dass das Ausgangsarray immer in drei Teilarrays aufgeteilt wird.
Hier einmal mein Code dazu:
public static void mergeNew(int[] A, int p, int r) {
int n1 = p + ((r + 1) / 3);
int n2 = (r + 1) - ((r + 1) - 2 * ((r + 1) / 3)) - (p + ((r + 1) / 3));
int n3 = (r + 1) - 2 * ((r + 1) / 3);
int[] L = new int[n1 + 1], M = new int[n2 + 1], R = new int[n3 + 1];
if ((r + 1) % 3 == 2) {
n2++;
n3--;
M = new int[n2 + 1];
R = new int[n3 + 1];
}
for (int i = 0; i < n1; i++) {
L[i] = A[p + i];
}
System.out.println("L:" + Arrays.toString(L));
for (int i = 0; i < n2; i++) {
M[i] = A[n1 + i];
}
System.out.println("M: " + Arrays.toString(M));
for (int i = 0; i < n3; i++) {
R[i] = A[n1 + n2 + i];
}
System.out.println("R: " + Arrays.toString(R));
L[n1] = Integer.MAX_VALUE;
M[n2] = Integer.MAX_VALUE; //Zeile 36
R[n3] = Integer.MAX_VALUE;
int i = 0;
int j = 0;
int l = 0;
for (int k = p; k <= r; k++) {
if (L[i] <= M[j]) {
if (L[i] <= R[l]) {
A[k] = L[i];
i = i + 1;
} else {
A[k] = R[l];
l = l + 1;
}
} else {
if (M[j] <= R[l]) {
A[k] = M[j];
j = j + 1;
} else {
A[k] = R[l];
l = l + 1;
}
}
}
}
Ansich denke ich persönlich nicht, dass das Problem bei diesr Methode liegt. Wenn ich dieser Methode z.B. ein Array übergebe was vie folgt aussieht:
{1, 5, 7, 3, 6, 10, 6, 7, 8}. Dann sortiert es dieses Array. Das Array was ich hier genommen habe besteht ja aus sozusagen drei Teilarrays die schon sortiert wurden.
Der Fehler liegt glaube ich eher bei der Rekursion:
public static int[] mergeSortNew(int[] a, int p, int r){
int q1, q2;
if (p < r){
q1 = p + ((r - p) / 3);
q2 = p + 2 * ((r - p) / 3) + 1;
mergeSortNew(a, p, q1);
mergeSortNew(a, q1 + 1, q2);
mergeSortNew(a,q2 + 1, r);
mergeNew(a, p, r);
}
return a;
}
Wenn ich nun diese Methode aufrufe mit folgender Zeile:
mergeSortNew(arr1, 0, arr1.length - 1);
Dann kriege ich folgende Fehlermeldung:
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 0
at Test.mergeNew(Test.java:36)
at Test.mergeSortNew(Test.java:70)
at Test.mergeSortNew(Test.java:68)
at Test.main(Test.java:6)
Ich habe die Zeile 36 markiert. Vielleicht sieht ja jemand den Fehler