K-Way MergeSort

[Kirby.exe]

Vielleicht bin einfach nur verwirrt, aber wir sollen unseren MergeSort Algorithmus in einen K-Way MergeSort Algorithmus umschreiben.

Hier ist die Aufgabenstellung:



Was hat t für eine Bedeutung? Ist es einfach die Anzahl der jeweiligen Aufspaltungen? Sprich bei t = 4 wird jedes mal in 4 kleinere Listen aufgespaltet?

 

[MoxxiManagarm]

Ja. Bei Mergesort werden jeweils 2 Subarrays betrachtet - links und rechts. Du hast nun t subarrays

 

[Kirby.exe]

Ok ich bin nur verwirrt wie ich das dann mache xD ich müsste ja irgendwie implementieren, dass man theoretisch auch 100000 Sub Arrays pro rekursion machen kann xD

 

[MoxxiManagarm]

Ja. Aber wo ist das Problem? Das hast du bei t=2 auch, wenn das Array eine ungerade Länge hat. Du machst halt so viele Subarrays wie möglich sind. Wenn du ein Array von n=7 hast und t=10, dann hast du halt nur 7 Subarrays, all diese 7 Subarrays haben die Länge n=1 und sind somit sortiert. Dein merge Schritt wird dann nur sehr aufwendig für große t. Letztlich ist der merge doch dann ein InsertionSort oder? 🤔

 

[Kirby.exe]

Mein Problem ist die implementierung xD ich verstehe nicht wie ich k-beliebige subarrays erstelle xD

 

[MoxxiManagarm]

Alle Subarrays haben die Länge n / t (Ganzzahldivision)
n % t Arrays besitzen diese Länge um 1 erhöht


Beispiel:
n = 7, t = 10 --> Alle Arrays haben die Länge 7 / 10 = 0, davon haben 7 % 10 = 7 eine um 1 größere Länge, also 1
n = 12, t = 5 --> Alle Arrays haben die Länge 12 / 5 = 2, davon haben 12 % 5 = 2 eine um 1 größere Länge, also 3.

 

[Kirby.exe]

Ahhhh ich verstehe Danke für die Erklärung

 

[Kirby.exe]

Alsoo ich habe mir ein wenig den Kopf zerbrochen und mir überlegt wie ich das implementieren könnte Für die Aufteilung in SubArrays hatte ich mir gedacht, dass ich die rekursiven aufrufe mit einer Schleife umschließe, welche bis k läuft xD Für den Merge habe ich mir bis jetzt noch nicht überlegt xD Ist diese Idee ein guter Ansatz oder schieße ich mit da mit der Laufzeit eher ins eigene Knie?

 

[kneitzel]

Ja, das hast Du aus meiner Sicht richtig gedacht.

 

[MoxxiManagarm]

Du hast ja die Anzahl s = n / t von Subarrays. Die Rückgabewerte der Rekursiven Aufrufe (int[]) kannst du in diesem s-langen Array speichern. Das musst du natürlich in einer Schleife machen.

 

[Kirby.exe]

Juut dann mache ich das mal xD Habe mal wieder viel zu kompliziert gedacht xD Dankee

 

[MoxxiManagarm]

Mir fällt gerade auf ich war eben selbst total verwirrt. s ist natürlich nicht n / t, s ist t falls t > n und n falls n < t

Zusammenfassend:
n - Länge des zu sortierenden Arrays
t - Anzahl der maximalen Partitionen
s - Anzahl der möglichen Partitionen mit Mindestlänge 1 -- n für t > n, t für t < n
m - Mindestlänge aller Partitionen (auch m = 0) -- n / t
k - Anzahl der Partionen mit der Länge m+1 -- n % t

 

[Kirby.exe]

Also ich muss sagen ich bin etwas verwirrt xD Ich habe etwas versucht...Bitte lacht mich nicht aus xD

private static void split(ArrayList<Integer> list, int k) {
        ArrayList<ArrayList<Integer>> subarrays = new ArrayList<>();
        int partitions = k > list.size() ? list.size():k;
        int factor = list.size()%k;
        int minLength = list.size()/k;
        int counter = 0;
        System.out.println("Partitions: " + partitions);
        System.out.println("Factor(m+1): " + factor);
        System.out.println("Minimum Length: " + minLength);
        for(int i = 0,m = 0; i < partitions; i++) {
            ArrayList<Integer> item = new ArrayList<>();
            if(list.size()-counter < 2) {minLength = list.size()-counter;}
            System.out.println("Max: " + minLength);
            for(int j = 0; j < minLength; j++,m++) {
                item.add(list.get(m));
                counter++;
            }
            subarrays.add(item);
            System.out.println("Subarray: " + subarrays.toString());
        }
        System.out.println("Whole List: " + list);
        System.out.println("Subarray: " + subarrays.toString());
    }

Ich versuche gerade erstmal es hinzubekommen die Liste in k-Teil Arrays aufzusplitten

 

[temi]

Kann sein, dass ich mich irre, aber bisher hattest du eine Teilung 2, was zu genau zwei Listen führt, nämlich "l" und "r".

Jetzt hast du eine Teilung von k Listen, damit sind "l" und "r" doch obsolet, oder? Genauso wie midIndex?

 

[Kirby.exe]

Also l und r werden gar nicht verwendet xD Die stehen nur noch da xD Ich kann es mal eben weglöschen Was mir auffällt...Meine Lösung funktioniert wenn die Länge der Liste und das k teiler sind ( z.B. länge = 100, k = 10). Wenn ich jedoch länge = 106 und k = 10 eingebe, werden die letzten Zahlen nicht bearbeitet, zumindest sieht es so aus xD

 

[Kirby.exe]

So ich habe es nun auch für nicht direkte Teiler geschafft xD

private static void split(ArrayList<Integer> list, int k) {
        ArrayList<ArrayList<Integer>> subarrays = new ArrayList<>();
        int partitions = k > list.size() ? list.size() : k;
        int rest = list.size()%k;
        int minLength = list.size()/k;
        int counter = partitions;
        
        System.out.println("Partitions: " + partitions);
        System.out.println("Factor(m+1): " + rest);
        System.out.println("Minimum Length: " + minLength);
        
        for(int i = 0,m = 0; i < partitions; i++) {
            ArrayList<Integer> item = new ArrayList<>();
            if(counter == 1) {minLength += rest;}
            
            System.out.println("Max: " + minLength + " | Counter: " + counter + " | List Length: " + list.size());
            
            for(int j = 0; j < minLength; j++,m++) {
                item.add(list.get(m));
            }
            subarrays.add(item);
            counter--;
            System.out.println("Subarray: " + subarrays.toString());
        }
        System.out.println("Whole List: " + list);
        System.out.println("Subarray: " + subarrays.toString());
    }

 

[Kirby.exe]

Edit: Ich hatte @MoxxiManagarm etwas falsch verstanden xD Habe es jetzt so umgesetzt:

private static void split(ArrayList<Integer> list, int k) {
        ArrayList<ArrayList<Integer>> subarrays = new ArrayList<>();
        int partitions = k > list.size() ? list.size() : k;
        int rest = list.size()%k;
        int minLength = list.size()/k;
        int counter = rest;
        int run = minLength+1;
        
        System.out.println("Partitions: " + partitions);
        System.out.println("Factor(m+1): " + rest);
        System.out.println("Minimum Length: " + minLength);
        
        for(int i = 0,m = 0; i < partitions; i++) {
            ArrayList<Integer> item = new ArrayList<>();
            if(counter == 0) {run = minLength;}
            
            System.out.println("Max: " + run + " | Counter: " + counter + " | List Length: " + list.size());
            
            for(int j = 0; j < run; j++,m++) {
                item.add(list.get(m));
            }
            subarrays.add(item);
            counter--;
            System.out.println("Subarray: " + subarrays.toString());
        }
        System.out.println("Whole List: " + list);
        System.out.println("Subarray: " + subarrays.toString());
    }

 

[Kirby.exe]

Also ich versuche gerade die merge-Methode dazu zu implementieren, aber ich bekomme eine OutOfBounds (das liegt daran dass er außerhalb der "r"-Index Grenzen schaut. Jedoch bin ich ehrlich gesagt verwirrt, was ich falsch mache xD

Hier ist mein aktueller Code:

Spoiler: sort

public static <T extends Comparable<? super T>> void sort(List<T> list) {
        if(list.size() < 2) {
            return;
        }
       
        ArrayList<ArrayList<T>> subarrays = new ArrayList<>();
        int partitions = t > list.size() ? list.size() : t;
        int rest = list.size()%t;
        int minLength = list.size()/t;
        int counter = rest;
        int run = minLength+1;
       
        System.out.println("Partitions: " + partitions);
        System.out.println("Factor(m+1): " + rest);
        System.out.println("Minimum Length: " + minLength);
       
        for(int i = 0,m = 0; i < partitions; i++) {
            ArrayList<T> item = new ArrayList<>();
            if(counter == 0) {run = minLength;}
           
            System.out.println("Max: " + run + " | Counter: " + counter + " | List Length: " + list.size());
           
            for(int j = 0; j < run; j++,m++) {
                item.add(list.get(m));
            }
            subarrays.add(item);
            counter--;
        }
        System.out.println("Whole List: " + list);
        System.out.println("Subarray: " + subarrays.toString());
       
        for(int i = 0; i < subarrays.size(); i++) {
            sort(subarrays.get(i));
        }
        System.out.println("Sackfressenliste: " + subarrays.get(0) + " " + subarrays.get(1));
        merge(list, subarrays.get(0), subarrays.get(1), list.size()/2, list.size() - (list.size()/2));
     
    }

Spoiler: merge

private static <T extends Comparable<? super T>> void merge(List<T> list, List<T> l, List<T> r, int left, int right) {
        System.out.println("Hey Bud!");
        System.out.println("Left Bound: " + left + " | Right Bound: " + right);
        System.out.println("List at Merge Begin: " + list.toString() + " | Subarray Left: " + l + " | Subarray Right: " + r);
        int i = 0, j = 0, k = 0;
        boolean check = false;
        while (i < left && j < right) {
            check = l.get(i) == null ? true : false;
            System.out.println("Loop Checker: " + check + " | i =" + i + ", j = " + j);
            if (l.get(i).compareTo(r.get(j)) <= 0) {
                list.set(k++, l.get(i++));
                System.out.println("Go IF | " + list.toString());
            }else {
                list.set(k++, r.get(j++));
                System.out.println("Go Else | " + list.toString());
            }
        }
     
        while (i < left) {
            list.set(k++, l.get(i++));
        }
        while (j < right) {
            list.set(k++, r.get(j++));
        }
       
        System.out.println("Subarray: " + list.toString());
    }

 

[Kirby.exe]

Edit: Die OutOfBounds liegt daran, dass die Main Liste viel zu groß...ich verstehe ehrlich gesagt nicht warum

 

[Kirby.exe]

Also hier ist meine Testklasse:

Spoiler: Testklasse

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

public class TestTMerge {

    public static void main(String[] args) {
        ArrayList<Integer> t = new ArrayList<>();
        fill(t, 7);
        TWayMergeSort.setT(4);
        System.out.println(t.toString());
        TWayMergeSort.sort(t);
        System.out.println(t.toString());
    }
    
    private static void fill(ArrayList<Integer> list, int size) {
        Random l = new Random();
        for(int i = 0; i < size; i++) {
            list.add(10+ l.nextInt(100));
        }
    }
    
    private static void fillList(ArrayList<Integer> list, int size) {
        Random l = new Random();
        for(int i = 0; i < size; i++) {
            list.add(l.nextInt(Integer.MAX_VALUE));
        }
    }

}

Das ist die Ausgabe mit der obigen Testklasse:

[90, 35, 58, 53, 77, 77, 103]
Partitions: 4
Factor(m+1): 3
Minimum Length: 1
Max: 2 | Counter: 3 | List Length: 7
Max: 2 | Counter: 2 | List Length: 7
Max: 2 | Counter: 1 | List Length: 7
Max: 1 | Counter: 0 | List Length: 7
Whole List: [90, 35, 58, 53, 77, 77, 103]
Subarray: [[90, 35], [58, 53], [77, 77], [103]]
Partitions: 2
Factor(m+1): 2
Minimum Length: 0
Max: 1 | Counter: 2 | List Length: 2
Max: 1 | Counter: 1 | List Length: 2
Whole List: [90, 35]
Subarray: [[90], [35]]
Sackfressenliste: [90] [35]
Liste: [90, 35]
Hey Bud!
Left Bound: 1 | Right Bound: 1
List at Merge Begin: [90, 35] | Subarray Left: [90] | Subarray Right: [35]
Go Else | [35, 35]
Subarray: [35, 90]
Partitions: 2
Factor(m+1): 2
Minimum Length: 0
Max: 1 | Counter: 2 | List Length: 2
Max: 1 | Counter: 1 | List Length: 2
Whole List: [58, 53]
Subarray: [[58], [53]]
Sackfressenliste: [58] [53]
Liste: [58, 53]
Hey Bud!
Left Bound: 1 | Right Bound: 1
List at Merge Begin: [58, 53] | Subarray Left: [58] | Subarray Right: [53]
Go Else | [53, 53]
Subarray: [53, 58]
Partitions: 2
Factor(m+1): 2
Minimum Length: 0
Max: 1 | Counter: 2 | List Length: 2
Max: 1 | Counter: 1 | List Length: 2
Whole List: [77, 77]
Subarray: [[77], [77]]
Sackfressenliste: [77] [77]
Liste: [77, 77]
Hey Bud!
Left Bound: 1 | Right Bound: 1
List at Merge Begin: [77, 77] | Subarray Left: [77] | Subarray Right: [77]
Go IF | [77, 77]
Subarray: [77, 77]
Sackfressenliste: [35, 90] [53, 58]
Liste: [90, 35, 58, 53, 77, 77, 103]
Hey Bud!
Left Bound: 3 | Right Bound: 4
List at Merge Begin: [90, 35, 58, 53, 77, 77, 103] | Subarray Left: [35, 90] | Subarray Right: [53, 58]  // <---
Go IF | [35, 35, 58, 53, 77, 77, 103]      // <----
Go Else | [35, 53, 58, 53, 77, 77, 103]   // <---
Go Else | [35, 53, 58, 53, 77, 77, 103]   // <----
Exception in thread "main" java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2
    at java.base/jdk.internal.util.Preconditions.outOfBounds(Preconditions.java:64)
    at java.base/jdk.internal.util.Preconditions.outOfBoundsCheckIndex(Preconditions.java:70)
    at java.base/jdk.internal.util.Preconditions.checkIndex(Preconditions.java:248)
    at java.base/java.util.Objects.checkIndex(Objects.java:372)
    at java.base/java.util.ArrayList.get(ArrayList.java:458)
    at TWayMergeSort.merge(TWayMergeSort.java:64)
    at TWayMergeSort.sort(TWayMergeSort.java:54)
    at TestTMerge.main(TestTMerge.java:11)

Ich verstehe nicht ganz woher diese riesige Liste kommt? Eigentlich sollte die Liste doch nur Länge 4 haben und habe ich wo anders einen Denkfehler?

 

[kneitzel]

Also ich kapiere nicht, was Du da überhaupt machst! Du teilst in 4 Arrays auf. Aber dann meinst Du, Du machst ein einfaches merge von nur zwei Listen. Und denen gibst Du die Längen mit, als ob Du die Liste in nur zwei Teile geteilt hättest.

Also Du übergibst zwei Listen der Länge 2 aber als Grenzen / Größe gibst Du mit: 4 und 3. Und sobald er dann auf das dritte Element (index: 2) zugreifen will, dann geht das natürlich nicht und du bekommst ein "java.lang.IndexOutOfBoundsException: Index 2 out of bounds for length 2"

Daher: Wenn Du in mehrere Teilarrays aufteilst, dann musst Du auch beim merge die ganzen Teilarrays berücksichtigen.
Und hatte ich es nicht auch schon im eigentlichen Merge Thread mal geschrieben: Hier die Längen zu übergeben ist doch quatsch! Die Listen alleine reichen, denn die Länge kannst Du da ja aus der Liste entnehmen. Was Du hier also schlicht hast sind redundante Parameter und wenn du diese falsch füllst, dann läufst du in Fehler. Und genau diese Fehler sind extrem unnötig.

 

[Kirby.exe]

Okee Ist es denn richtig im merge immer nur jeweils zwei Arrays zusammen zu mergen ? Es verwirrt mich insofern, dass ich gedacht haben, dass die zwei subarrays in eine, meiner Meinung nach zu großen Liste gemerged werden, bsp. [13,35] und [15,26] ---> [13,15,26,35] so gemerged werden hier wäre die Liste Länge 4. Jedoch in dem letzten ausgeführten Schritt werden die zwei "zweier Listen" in eine 7er Liste gemerged.

 

[kneitzel]

Da ist die Frage, was vorgegeben wurde. Generell ist beides möglich und denkbar. Du kannst direkt alle Arrays zusammen mergen oder Du geht iterativ her und merged immer 2 Listen. Und dann ist auch die Frage, wie du hier vorgehen möchtest - da gibt es dann auch diverse Möglichkeiten.

Das kann man auch alles nachlesen z.B. unter https://en.wikipedia.org/wiki/K-way_merge_algorithm

 

[Kirby.exe]

Da gesagt wurde, dass wir unseren bereits implementierten Algorithmus für MergeSort umschreiben sollen, vermute ich dass wir in 2er Schritten mergen sollen xD Also die merge Methode glaube ich verstanden zu haben:

private static <T extends Comparable<? super T>> void merge(List<T> list, List<T> l, List<T> r) {
        int i = 0, j = 0, k = 0;
        while (i < l.size() && j < r.size()) {   
            if (l.get(i).compareTo(r.get(j)) <= 0) { // <--- Vergleiche die Elemente aus den zwei Listen
                list.set(k++, l.get(i++));             // <--- Stecke ein Element der Liste l in "liste"
            }else {
                list.set(k++, r.get(j++));             // <---- Stecke ein Element der Liste r in "liste"
            }
        }
      
        while (i < l.size()) {
            list.set(k++, l.get(i++));    // <---- Stecke die verbleidenden Elemente aus l in die liste
        }
        while (j < r.size()) {
            list.set(k++, r.get(j++));    // <---- Stecke die verbleidenden Elemente aus r in die liste
        }
    }

 

[Kirby.exe]

So hatte ich mir das gedacht:

 

[kneitzel]

Das sieht von den Gedankengängen her doch gut aus. Dann musst du es nur noch implementieren.

Dazu evtl. einfach den Algorithmus in Worte fassen: was genau hast du da skizziert? Was ist da Dein Vorgehen?

 

[Kirby.exe]

Naja also ich spalte die Liste jeweils immer in k-subarrays auf und beim zusammenmergen von jeweils zwei Listen iteriere ich durch die Listen und vergleiche die Elemente nach der Größe xD

 

[kneitzel]

Die Aufteilung hast Du ja schon gemacht, und du hast da rekursive etwas aufgerufen... Und das Mergen von zwei Listen in eine Liste hast Du jetzt auch schon.

Du musst jetzt halt nur im Detail erläutern, wie Du das den n Listen über das Mergen von zwei Listen alles in eine Liste bekommen kannst.

 

[Kirby.exe]

Naja so wie ich es verstanden haben ist die übergebene Liste "list" immer die letzte Subliste(also von der Länge). Daher sollte ja eigentlich die Liste länger werden sprich:

[14,36],  [17,26]                            [0,4],  [9]
       |                                          |
       |___>[14,17,26,36]              [0,4,9]<___|
                  |                       |
                  |                       |
                  |_>[0,4,9,14,17,26,36]<_|

 

[Kirby.exe]

Das Problem ist die der merge-Aufruf mit subarrays.get(0) und subarrays.get(1) da in der letzten Iteration 4 Subarrays existieren, somit müsste ich die merge Methode auch in eine schleife stecken und diese bis subarrays.size() laufen lassen oder nicht?

So ich habe es in eine Schleife gesteckt und theoretisch war es richtig. Jetzt existiert nur noch das Problem, dass sich die Werte in der ganz Langen Liste überschreiben

Hier werden die in die große Liste gepackt, jedoch muss ich die Liste gedanklich mit bounds teilen und diese noch vergleichen oder bin ich auf dem Holzweg?

Hier ist mal die Konsolenausgabe für den Part den ich meine:

Die Subliste: [58, 68], [21, 34]
Liste: [68, 58, 34, 21, 68, 79, 100]
Go Else | [21, 58, 34, 21, 68, 79, 100]
Go Else | [21, 34, 34, 21, 68, 79, 100]
Subarray: [21, 34, 58, 68, 68, 79, 100]

Die Subliste: [68, 79], [100]
Liste: [21, 34, 58, 68, 68, 79, 100]
Go IF | [68, 34, 58, 68, 68, 79, 100]
Go IF | [68, 79, 58, 68, 68, 79, 100]
Subarray: [68, 79, 100, 68, 68, 79, 100]

 

[Kirby.exe]

Alsoo ich habe den Algorithmus "hinbekommen" und bereits abgegeben. Vorhin habe ich eine Rückmeldung bekommen, dass der Algorithmus, welchen ich implementiert habe nicht besonders effizient war xD Da ich in dem Fach eine Klausur schreiben und es vermutlich in meiner späteren IT-Karriere brauche, würde ich gerne verstehen und lernen wie man meinen "spagetti-code" in effizienten Code umschreibt xD Hier ist mein abgegebener Code:

Spoiler: TWAY Merge

import java.util.ArrayList;
import java.util.List;

public class TWayMergeSort {
    
    private static int t = 100;
    
    public static void setT(int tt) {
        if(tt>1) {
            t = tt;
        }else {
            t = 2;
        }
    }
  
    public static <T extends Comparable<? super T>> void sort(List<T> list) {
        if(list.size() < 2) {
            return;
        }
        
        ArrayList<ArrayList<T>> subarrays = new ArrayList<>();
        int partitions = t > list.size() ? list.size() : t;
        int rest = list.size()%t;
        int minLength = list.size()/t;
        int counter = rest;
        int run = minLength+1;
        
        for(int i = 0,m = 0; i < partitions; i++) {
            ArrayList<T> item = new ArrayList<>();
            if(counter == 0) {run = minLength;}
            
            for(int j = 0; j < run; j++,m++) {
                item.add(list.get(m));
            }
            subarrays.add(item);
            counter--;
        }
        
        for(int i = 0; i < subarrays.size(); i++) {
            sort(subarrays.get(i));
        }
        
        while(subarrays.size() > 1) {
            ArrayList<T> cur = new ArrayList<T>();
            merge(cur, subarrays.get(0), subarrays.get(1));
            subarrays.remove(0);
            subarrays.remove(0);
            subarrays.add(0, cur);
        }
        for (int i = 0, j = 0; i < subarrays.size(); ++i) {
            for (int k = 0; k < subarrays.get(i).size(); ++k) {
                list.set(j++, subarrays.get(i).get(k));
            }
        }
    }
  
    private static <T extends Comparable<? super T>> void merge(List<T> list, List<T> l, List<T> r) {
        int i = 0, j = 0, k = 0;
        
        while (i < l.size() && j < r.size()) {
            if (l.get(i).compareTo(r.get(j)) <= 0) {
                list.add(k++, l.get(i++));
            }else {
                list.add(k++, r.get(j++));
            }
        }
      
        while (i < l.size()) {
            list.add(k++, l.get(i++));
        }
        while (j < r.size()) {
            list.add(k++, r.get(j++));
        }
    }
}

 

[kneitzel]

In #23 habe ich einen Link gebracht, in dem das Thema behandelt wird. Das würde Dir auch helfen bezüglich Laufzeit des Algorithmus, was du auch behandelt hat, oder?

Du hast derzeit O(n*k) und O(n*log(k)) ist möglich. Das nur am Rande ....

 

[Kirby.exe]

Jap ich hatte mir den durchgelesen, jedoch wurde dort mit bäumen gearbeitet Ich werde es mir morgen nochmal im Detail durchlesen

 

[kneitzel]

Nein, da wurden mehrere Möglichkeiten vorgestellt. Das mit den Bäumen ist nur eine Möglichkeit, wie man k Teilarrays gleichzeitig mergen kann.