K-Way MergeSort

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

JustNobody

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_Sike

Kirby_Sike

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.
 
Zuletzt bearbeitet:
J

JustNobody

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_Sike

Kirby_Sike

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

JustNobody

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_Sike

Kirby_Sike

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
 
J

JustNobody

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_Sike

Kirby_Sike

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:

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

Kirby_Sike

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:

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

Kirby_Sike

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:

Java:
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++));
        }
    }
}
 
J

JustNobody

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_Sike

Kirby_Sike

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

JustNobody

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

K-Way MergeSort

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben