K-Way MergeSort

Diskutiere K-Way MergeSort im Allgemeine Java-Themen Bereich.
Kirby_Sike

Kirby_Sike

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

Hier ist die Aufgabenstellung:

Bildschirmfoto 2020-05-05 um 11.59.55.png

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

MoxxiManagarm

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

Kirby_Sike

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

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_Sike

Kirby_Sike

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

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_Sike

Kirby_Sike

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?
 
MoxxiManagarm

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_Sike

Kirby_Sike

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

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
 
Zuletzt bearbeitet:
Kirby_Sike

Kirby_Sike

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

Java:
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 :)
 
Zuletzt bearbeitet:
T

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_Sike

Kirby_Sike

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
 
Zuletzt bearbeitet:
Kirby_Sike

Kirby_Sike

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

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

Kirby_Sike

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

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

Kirby_Sike

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:

Java:
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));
     
    }
Java:
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());
    }
 
Zuletzt bearbeitet:
Kirby_Sike

Kirby_Sike

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

Kirby_Sike

Also hier ist meine Testklasse:
Java:
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:
Code:
[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?
 
Thema: 

K-Way MergeSort

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben