Merge Sort

Kirby.exe

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


Java:
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:

F8CA8590-5564-4B60-A00B-B8AEF08AD926.jpeg
 

httpdigest

Top Contributor
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

Top Contributor
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:

Mergeee.png
 
Zuletzt bearbeitet:

LimDul

Top Contributor
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

Top Contributor
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

Top Contributor
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

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

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++));
        }
    }
}
Java:
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:
Code:
[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]
 
K

kneitzel

Gast
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!
 
K

kneitzel

Gast
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:

Code:
            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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
L Stack overflow bei einer endrekursiven Funktion (Anwendung: Spezialform des Package Merge) Allgemeine Java-Themen 4
foobar Merge ints Allgemeine Java-Themen 10
R Formel Bubble Sort Allgemeine Java-Themen 1
M Bubble Sort Allgemeine Java-Themen 3
Aartiyadav Comparisons and Swapa in Bubble-sort Java Allgemeine Java-Themen 6
Cromewell Tail-Rekursiver Counting Sort Allgemeine Java-Themen 20
Kirby.exe Bucket Sort Allgemeine Java-Themen 7
A Heap-Sort Allgemeine Java-Themen 2
D Collections.sort funktioniert nicht in exportierten .class Dateien Allgemeine Java-Themen 10
J Array-List Bubble-Sort Allgemeine Java-Themen 12
M Arrays.sort Problem Allgemeine Java-Themen 2
B Counting Sort (Sortieren durch Zählen) Allgemeine Java-Themen 13
F File.listFiles ohne .sort Allgemeine Java-Themen 6
B Input/Output Schneller Sort mit wenigen Zugriffen (oder was anderes?) Allgemeine Java-Themen 3
A External Sort - too many open files Allgemeine Java-Themen 6
X einfach verkettete Liste und Insertion Sort Allgemeine Java-Themen 3
S Array-Sort mittels Binärsuche Allgemeine Java-Themen 2
M Insertion sort Allgemeine Java-Themen 13
K Bound mismatch: The generic method sort(List<T>) of ty Allgemeine Java-Themen 4
T Sortierung mit Collections.sort() Allgemeine Java-Themen 4
L-ectron-X Problem mit Collections.sort() mit Java 1.5 Allgemeine Java-Themen 9

Ähnliche Java Themen

Neue Themen


Oben