MergeSort (für Anfänger )

[HappyBienchen]

Hallo an Alle,
ich muss das MergeSort Verfahren implementieren, allerdings will das nicht wirklich klappen. Vielleicht kann mir jemand weiter helfen? Die Methode mergeSort wurde vom Professor schon vorgegeben.
Das hier habe ich bisher:

import java.util.Arrays;

public class MergeSort {

    public static void main(String[] args) {
        int[] array = {149, 45, 76, 0, 93, 15, 39, -5};
        mergeSort(array, 0, array.length-1);
        System.out.println("Sortiertes Array: " + Arrays.toString(array));

    }
// Sortieren des Teil-Arrays a[l]..a[r]

    private static void mergeSort(int[] a, int l, int r) {
        if (r <= l) { //rechts kleiner links
            return; // nur 1 Element => fertig.
        }
        int m = (l + r) / 2;
        mergeSort(a, l, m); // linke Hälfte sortieren
        mergeSort(a, m + 1, r); // rechte Hälfte sortieren
        merge(a, l, m, r); // beide Hälften zusammenmischen

    }
// Mischen der Teil-Arrays l..p und p+1..r

    private static void merge(int[] a, int l, int p, int r) {

        int[] sortedArray = new int[a.length];
        for (int k = l; k < r; k++) { 

            for (int i = 0; i < p; i++) {
                for (int j = p + 1; j < r; j++) {

                    if (a[j] <= a[i]) {
                        sortedArray[k] = a[j];
                        
                    } else {
                        sortedArray[k] = a[i];
                        
                    }
                }
            }
        }
    }
}

 

[DrZoidberg]

Am Ende der merge Methode musst Du den Inhalt von sortedArray nach a kopieren.
Ausserdem sollte es k <= r heissen und nicht k < r.
Und Du kannst auch nicht zwei verschachtelte Schleifen verwenden. Nimm eine while Schleife und erhöhe dann jeweils i bzw j. z.b. so

if (a[j] <= a[i]) {
    sortedArray[k] = a[j++];
} else {
    sortedArray[k] = a[i++];
}

 

[HappyBienchen]

Ich danke dir. Nun habe ich versucht das mal umzusetzen. Allerdings bekomme ich nun eine ArrayIndexOutOfBoundsException

 private static void merge(int[] a, int l, int p, int r) {

        int[] sortedArray = new int[a.length];
        for (int k = l; k <= r; k++) { // neues array befüllen

            int i = 0;
            int j = p + 1;
            while (i <= p) {

                if (a[j] <= a[i]) {
                    sortedArray[k] = a[j];
                    j++;
                } else {
                    sortedArray[k] = a[i];
                    i++;
                }
            }
        
        a[k] = sortedArray[k];
    }
}
}

 

[JavaMeister]

Was sagt google dazu?

 

[DrZoidberg]

So könnte es gehen

private static void merge(int[] a, int l, int p, int r) {
    int[] sortedArray = new int[r-l+1];
    int i = l;
    int j = p + 1;
    for(int k = 0; k < sortedArray.length; k++) {
        if(i > p || (j <= r && a[i] > a[j])) {
            sortedArray[k] = a[j];
            j++;
        } else {
            sortedArray[k] = a[i];
            i++;
        }
    }
    for(int k = 0; k < sortedArray.length; k++) {
        a[k+l] = sortedArray[k];
    }
}

 

[HappyBienchen]

Vielen dank, das probiere ich mal aus

 

[HappyBienchen]

Ich habe eine Frage zu deiner if-Abfrage.
In welchem Punkt kann i > p sein, wenn doch der erste teil des arrays von i= links und p = mitte geht und innerhalb dieser grenzen schon sortiert ist?

leider bekomme ich aber noch immer eine ArrayIndexOutOfBoundException

 

[JavaMeister]

Was steht in der Zeile in der die Exception kommt?

Wieso debuggst du nicht die indexe dort?

Ist dir klar, wie so eine Exception kommt und warum?

 

[DrZoidberg]

Stell dir mal vor das Array sieht so aus
int[] a = {1,2,3,7,8};
und du schreibst dann merge(a, 0, 2, 4);
Dann kopiert die Methode erstmal 1,2 und 3 nach sortedArray, danach ist i dann 3 also zu gross.
Mit anderen Worten, wenn eine der beiden Hälften komplett abgearbeitet ist (i > p oder j > r), dann kann man nur noch aus der anderen Hälfte lesen.

Hier mal ein komplettes Programm. Funktioniert bei mir einwandfrei.

import java.util.Arrays;
import java.util.Random;

public class MergeSort {
    private static void mergeSort(int[] a, int l, int r) {
        if (r <= l) {
            return;
        }
        int m = (l + r) / 2;
        mergeSort(a, l, m);
        mergeSort(a, m + 1, r);
        merge(a, l, m, r);
    
    }

    private static void merge(int[] a, int l, int p, int r) {
        int[] sortedArray = new int[r-l+1];
        int i = l;
        int j = p + 1;
        for(int k = 0; k < sortedArray.length; k++) {
            if(i > p || (j <= r && a[i] > a[j])) {
                sortedArray[k] = a[j];
                j++;
            } else {
                sortedArray[k] = a[i];
                i++;
            }
        }
        for(int k = 0; k < sortedArray.length; k++) {
            a[k+l] = sortedArray[k];
        }
    }
    
    public static void main(String[] args) throws Exception {
        Random rand = new Random();
        int[] a = new int[1000];
        for(int i = 0; i < a.length; i++) {
            a[i] = rand.nextInt(100);
        }

        mergeSort(a, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }
}

 

[HappyBienchen]

Ich danke dir 🙂
Ich habe meinen Fehler gefunden.
Für das sortedArray habe ich, anders als du, Speicher reserviert in Höhe von a.length. Du Hingegen hast ja (r-l+1) geschrieben. Daran hats gelegen.