Merge Sort

[Kirby.exe]

Alsoo ich bin ultimativ verwirrt...Ich soll eine Merge Sort Methode implementieren. Dazu habe einen rekursiven Algorithmus gefunden:

public static <T extends Comparable<? super T>> void sort(List<T> list, int lowIndex, int highIndex){
    if(lowIndex == highIndex){
        return;
    }else{
        int midIndex = (lowIndex+highIndex)/2;
        sort(list, lowIndex, midIndex);
        sort(list, midIndex+1, highIndex);
        merge(); // <--- Die hier möchte ich gerne aufstellen
    }
}

Ich würde gerne die merge Methode aufstellen, jedoch verstehe ich nicht wirklich wie ich anfangen soll xD Ehrlich gesagt stehe ich etwas auf Kriegsfuß mit Rekursion 🙁

Ich habe hier einfach mal den Rekursionsbaum für eine Liste der Länge 4 gezeichnet:

 

[httpdigest]

Die merge() Methode bei Mergesort selbst hat nicht mehr viel mit Rekursion zu tun. Diese Methode ist selber ja nicht rekursiv. Sie soll einfach nur zwei bereits sortierte Bereiche entgegennehmen und diese "zusammenmergen". Das kannst du tun, indem du einfach zwei Cursor/Pointer für den einen und den anderen Bereich definierst, und immer dann für einen der beiden Bereiche hochzählst, wenn das aktuelle Element in diesem Bereich kleiner als oder gleich dem aktuellen Element im anderen Bereich ist.

 

[Kirby.exe]

Ich weiß xD Die merge() Methode ist iterativ xD Mein Problem ist, dass ich nur begrenzt verstehe, was die sort() Methode überhaupt tut xD So wie ich es verstanden habe ist Merge Sort entwickelt nach dem Prinzip Divide and Conquer, also vermute ich dass die sort Methode die liste unterteilt bis man nur noch jeweils zwei Elemente zu vergleichen hat und dann die Liste wieder zusammenfügt und genau das verwirrt mich total xD

Also so:

 

[LimDul]

Bei deinem Bildern ist die Merge Methode falsch.

Aus Links (2,6) und Rechts (3,5) wird im Merge nicht (2,6,3,5) sondern direkt (2,3,5,6).

Die Merge Methode baut direkt aus zwei sortierten Arrays ein großes Sortiertes Array auf. Dazu geht sie bei beiden Arrays "gleichzeitig" durch. Und in jedem durchlauf wird entweder das nächste Element als dem linken array in das Zielarray übernommen oder das nächste element als dem rechten Arrays (und dann wandert in dem Array, wo das Element rausgepickt wurde, der index eins weiter).

Das heißt, in dem Fall würde das Zielarray in 4 Schritten wie folgt aufgebaut:
(2) => (2,3) => (2,3,5) => (2,3,5,6)

 

[Kirby.exe]

Ok das habe ich soweit verstanden, aber muss die merge() Methode meine Liste nicht erstmal zerstückeln? xD Soweit ich sehe macht die sort() Methode es ja nicht xD

 

[LimDul]

Oh - hast vollkommen Recht. Ich kannte Mergesort nur als Variante, wo wirklich neue Arrays erzeugt werden.


(2,6,3,5) kommt aus den beiden Sort-Methoden raus. Da muss man dann beim mergen dennoch so vorgehen wie ich beschrieben habe - mit dem Unterschied das die beiden Arrays (2,6) und (3,5) nicht als echte einzelne Arrays existierten und das Zielarray ebenfalls kein eigenes ist.

 

[Kirby.exe]

Na ich probiere mal mein Glück xD Thx für die erklärung 🙂

 

[Kirby.exe]

Alsoooo Ich habe folgende Klassen aufgesetzt, aber ehrlich gesagt sehe ich meinen Fehler nicht....Ich hoffe jemand von euch entdeckt ihn 🙂

Spoiler: MergeSort.java

public class MergeSort {
   
   
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        mergeSort(list, list.size());
    }
   
    private static <T extends Comparable<? super T>> void mergeSort(List<T> list, int n) {
        if(n < 2) {
            return;
        }
       
        int midIndex = n/2;
        ArrayList<T> l = new ArrayList<>(midIndex);
        ArrayList<T> r = new ArrayList<>(n-midIndex);
   
        for (int i = 0; i < midIndex; i++) {
            l.add(i, list.get(i));
        }
        for (int i = midIndex; i < n; i++) {
            r.add(i-midIndex, list.get(i));
        }
       
        mergeSort(l, midIndex);
        mergeSort(r, n - midIndex);
        System.out.println("Aktuelles n: " + n);
        merge(list, l, r, midIndex, n - midIndex);
       
    }
   
    private static <T extends Comparable<? super T>> void merge(List<T> list, List<T> l, List<T> r, int left, int right) {
       
        int i = 0, j = 0, k = 0;
        while (i < left && j < right) {
            System.out.println("Our i: " + l.get(i) + " and Our j: " + r.get(j));
            if (l.get(i).compareTo(r.get(j)) <= 0) {
                System.out.println("If");
                list.set(k++, l.get(i++));
                System.out.println("Our list in the IF: " + list.toString());
            }else {
                System.out.println("Else");
                list.set(k++, l.get(j++));
                System.out.println("Our list in the Else: " + list.toString());
            }
        }
       
        while (i < left) {
            list.set(k++, l.get(i++));
        }
        while (j < right) {
            list.set(k++, r.get(j++));
        }
    }
}

Spoiler: Test Klasse

import java.util.ArrayList;
import java.util.Random;

public class MergeSortTest {

    public static void main(String[] args) {
        ArrayList<Integer> k = new ArrayList<>();
        //fillList(k, 5);
        fillListString(k, "1846");
        System.out.println(k.toString());
        MergeSort.sort(k);
        System.out.println(k.toString());
    }
   
    private static void fillList(ArrayList<Integer> list, int size) {
        Random l = new Random();
        for(int i = 0; i < size; i++) {
            list.add(l.nextInt(1000));
        }
    }
   
    private static void fillListString(ArrayList<Integer> list, String s) {
        for(int i = 0; i < s.length(); i++) {
            list.add(Integer.parseInt("" + s.charAt(i)));
        }
    }

}

Meine fehlerhafte Ausgabe:

[1, 8, 4, 6]
Aktuelles n: 2
Our i: 1 and Our j: 8
If
Our list in the IF: [1, 8]
Aktuelles n: 2
Our i: 4 and Our j: 6
If
Our list in the IF: [4, 6]
Aktuelles n: 4
Our i: 1 and Our j: 4
If
Our list in the IF: [1, 8, 4, 6]
Our i: 8 and Our j: 4
Else
Our list in the Else: [1, 1, 4, 6]
Our i: 8 and Our j: 6
Else
Our list in the Else: [1, 1, 8, 6]
[1, 1, 8, 8]

 

[kneitzel]

Und dein merge ist nicht korrekt. Er fügt immer aus l ein statt einmal aus l und einmal aus k.

Und nur ein paar Anregungen:
a) ++ Operator würde ich nie mit anderen Befehlen mischen. Die Lesbarkeit leidet dadurch stark.
b) der Parameter n bei merge ist doch immer die Größe der Liste, daher unnötig!

 

[Kirby.exe]

K ist doch nur meine Zähler Variable in der merge() methode xD

 

[kneitzel]

Das zweite Array heisst r -> Vergib ordentliche Namen, dann hat man nicht diese einfachen Tippfehler.

Ändert aber nichts daran, dass Du zwei mal l.get(..) machst:

            if (l.get(i).compareTo(r.get(j)) <= 0) {
                list.set(k++, l.get(i++));
            }else {
                list.set(k++, l.get(j++));
            }

Evtl. ohne die blöde Ausgabe, die nichts bringt leichter zu sehen.

Im Else Zweig musst Du natürlich list.set(k++, r.get(j++)); haben.

 

[Kirby.exe]

Stimmt jetzt sehe ich es auch 🙁 Dankeschön für deine hilfe 🙂