MergeSort allgemein

Bitte aktiviere JavaScript!
Hallo,
ich habe Probleme, den allgemeinen Mergesort zu implementieren. Es geht darum, das zu sortierende Array nicht zu halbieren, sondern beliebig zu teilen.
Es soll dabei eine Klassenvariable x für die Anzal der Teilfelder verwendet werden.
Java:
private static int x = 100;
public static void setT(int tt) {
    if(xx>1) x = xx;
    else x = 2;
}
Ich kann mir nicht vorstellen, wie ich im Vergleich zu dem Halbierungsverfahren des normalen Mergesort vorgehen soll.
Kann mir jmd vllt einen Tipp geben, wie ich das Problem angehen könnte?
 
A

Anzeige




Vielleicht hilft dir unser Kurs hier weiter —> (hier klicken)
Also liegt das Problem beim Verständnis?
Spielen wir es einmal mit x = 3 durch und wir haben ein Array mit 8 Feldern: 2,1,7,8,9,4,5,6

Nun ist erst einmal die Frage nach der Aufteilung. Wie können wir die 8 Felder in 3 Gruppen aufteilen?
Dazu können wir zuerst Berechnen: 8/3 = 2 also mindestens 2 Felder pro Aufruf werden genommen.
Aber wir sehen direkt: 3* 2 Felder bedeutet, dass wir nur 6 Felder behandelt haben. Das ist doof und bedeutet einfach nur, dass wir noch den rest der Berechnung beachten müssen: 8%2 = 2, d.h. die ersten zwei Aufrufe bekommen jeweils ein Feld mehr mit.

Nun nehmen wir noch einen Spezialfall: Wir nehmen das Array mit 3 Felden: 1,2,3
Und nun wollen wir ein Mergesort mit 5 parallelen Aufrufen.
Hier ist jetzt 3 < 5, d.h. wir machen nur 3 Aufrufe mit jeweils einem Element.

Somit kommen wir jetzt erst einmal zurück und machen es ganz allgemein:
Wir haben n Elemente und wollen Mergesort mit x parallelen Aufrufen:
Ist x > n= Dann: n Aufrufe mit nur einem Element.
Sonst: x Aufrufe mit n/x Elemente wobei die ersten n%x Elemente ein Element mehr mitgegeben bekommen.

Dann kommt der zweite Part: Merge von n Arrays.
- Bei zwei Arrays hast Du immer das Minimum von einer der beiden Listen genommen.
- Dieses Minimum hast Du im Ziel eingefügt
- Und dann in der Liste entfernt bzw. bist weiter gegangen.

Das Ganze kann man auch generisch mit beliebig vielen Listen ausdrücken:
- Minimum ist null, Liste von Minimum ist null.
- für jede Liste von Werten, die nicht leer sind, prüfe ob das derzeitige Minimum null ist oder ob das Minimum kleiner ist als der aktuelle Wert der Liste. Wenn das der Fall ist: Minimum ist Wert aus der Liste, Liste von Minimum ist die aktuelle Liste
- Fall ein Minimum gefunden: Füge Minimum zum Ziel hinzu, nimm den Wert aus der Liste von Minimum. Und fange von vorne an.
- falls kein Minimum gefunden (Alle Teil-Listen sind leer!), dann merge fertig.

Damit hätten wir den Algorithmus doch fertig und man muss diesen nur noch umsetzen.
 
Nun ist erst einmal die Frage nach der Aufteilung. Wie können wir die 8 Felder in 3 Gruppen aufteilen?
Dazu können wir zuerst Berechnen: 8/3 = 2 also mindestens 2 Felder pro Aufruf werden genommen.
Aber wir sehen direkt: 3* 2 Felder bedeutet, dass wir nur 6 Felder behandelt haben. Das ist doof und bedeutet einfach nur, dass wir noch den rest der Berechnung beachten müssen: 8%2 = 2, d.h. die ersten zwei Aufrufe bekommen jeweils ein Feld mehr mit.
Danke für deine schnelle Anwort:)
Ich verstehe nicht, was du mit die ersten 2 Aufrufe bekommen jeweils ein Feld mehr mit, meinst. Wie wäre das im konkreten Fall?
Wie kommst auf 8%2=2? Wäre der Rest nicht 0?
 
Danke für deine schnelle Anwort:)
Ich verstehe nicht, was du mit die ersten 2 Aufrufe bekommen jeweils ein Feld mehr mit, meinst. Wie wäre das im konkreten Fall?
Wie kommst auf 8%2=2? Wäre der Rest nicht 0?
Schreibfehler ... sollte natürlich 8%3 heissen. Wir haben ja 8 Felder im Array und wollen es auf 3 Elemente aufteilen. Dazu brauchen wir n%x = 8%3=2 Listen mit n/x= 8/3+1=3 Feldern und die restlichen x - n%x = 3-(8%2)=1 List(en) mit n/x=8/3=2 Feldern. (Somit haben wir 3 Listen mit 3, 3, 2 Feldern somit sind alle 8 Felder abgedeckt.)

Das ist also wie Bonbons aufteilen. Wir haben 8 Bonbons und 3 Kinder.

Jedes Kind kann auf jeden Fall 8/3 Bonbons bekommen. Da bleiben dann aber 8%3 (2) Bonbons übrig. Und die müssen wir natürlich auch abgeben, also geben wir den ersten zwei Kindern einfach eins mehr.
 
Ich kann mir nicht vorstellen, wie ich im Vergleich zu dem Halbierungsverfahren des normalen Mergesort vorgehen soll.
Kann mir jmd vllt einen Tipp geben, wie ich das Problem angehen könnte?
Also es macht keinen Sinn kein Halbierungsverfahren zu verwenden. Außer Du meinst den "Natürlichen Mergesort".

Natural Mergesort (natürliches Mergesort) ist eine Erweiterung von Mergesort, die bereits vorsortierte Teilfolgen, so genannte runs, innerhalb der zu sortierenden Startliste ausnutzt. Die Basis für den Mergevorgang bilden hier nicht die rekursiv oder iterativ gewonnenen Zweiergruppen, sondern die in einem ersten Durchgang zu bestimmenden runs:

Das bedeutet Du durchläufst die Daten einmal linear und bestimmst bereits sortierte Teilmengen (runs).
Auf diese wendest Du dann Mergsort an.
 
EIn Element ist doch sortiert. Muss da nicht dann die Methode abrechen?
Ja, da ist die Frage, wie man das Abbruch-Kriterium implementiert.

Normal ist halt, dass man im rekursiven Aufruf einen Check hat: if Abbruchbedingung then return definiertenWert.
Hier kann man dann natürlich drüber reden, ob man diesen Check in den Aufruf mit herein packt - und dann den Aufruf einfach weglässt.
Hier kann man nicht von richtig oder falsch reden. Ich würde es ggf. im Code ausprobieren und dann das besser lesbare nehmen.

Aber generell würde ich hier die Regel "No Optimizations" anwenden. diese Optimierungen bringen unter dem Strich nicht viel, Kosten Zeit, bringen das zusätzliche Risiko von Fehlern und werden leicht unübersichtlich.
Und dann noch "KISS" - Keep it simple, stupid. Also das mit der Abbruchbedingung ist das Schema F, das man einfach anwenden kann und jede Änderung verkompliziert es - und es ist eben nicht mehr einfach ("simple") und man muss überlegen, was gemacht wurde (es ist nicht mehr "stupid").

Also es macht keinen Sinn kein Halbierungsverfahren zu verwenden. Außer Du meinst den "Natürlichen Mergesort".

Natural Mergesort (natürliches Mergesort) ist eine Erweiterung von Mergesort, die bereits vorsortierte Teilfolgen, so genannte runs, innerhalb der zu sortierenden Startliste ausnutzt. Die Basis für den Mergevorgang bilden hier nicht die rekursiv oder iterativ gewonnenen Zweiergruppen, sondern die in einem ersten Durchgang zu bestimmenden runs:

Das bedeutet Du durchläufst die Daten einmal linear und bestimmst bereits sortierte Teilmengen (runs).
Auf diese wendest Du dann Mergsort an.
Ja, da ist die Frage, in wie weit dies als nächste Optimierung vorgesehen ist. Das könnte die Vorstufe sein, um eben das zu implementieren. Teilsortierte Mengen nehmen um diese nicht mehr sortieren zu müssen und um dann gleich einen Merge von diesen machen zu können. Aber man muss dazu von der Unterteilung in zwei Bereiche runter, oder? (Ist irgendwie zu lange her, dass ich mich mit solchen Dingen auseinander gesetzt habe :) )
 
Java:
public static void mergesort (List<T> a, int low, int high, int x) {
        if (low < high) {
            for (int i = 0; i < x; i++) {
                mergesort (a,low + i*(high-low+1)/x, low + (i+1)*(high-low+1)/x - 1,x);
            }
            merge (a, low, high, x);
}
Ich bin nicht ganz sicher.
Was sagst du
 
Das sieht sehr gut aus würde ich sagen. Habe es jetzt auch nur etwas geprüft und die Berechnung der Teile sieht sehr gut aus.

Jetzt bin ich gespannt, was für ein merge du baust. (Du hast über die Problematik sehr gut nachgedacht und es gut gelöst. In der Erläuterung habe ich ja ganz anders für Dein Verständnis beschrieben, als Du es dann gebaut hast. Sehr gut!)
 
Vielen Dank:)
Bei merge muss ich ja beliebig viele Listen anlegen. Wie geht das denn überhaupt technisch?
Ich weis auch noch nicht warum du eine Liste von Minima brauchst.
Du schreibst: Liste von Minimum ist null.?
 
Wenn Du bei zwei Listen das merge gemacht hast, hast Du immer geprüft:
- Haben beide Listen noch Elemente? => Minimum finden.
- Hat Liste 1 noch Elemente? => Diese Werte kopieren
- Hat Liste 2 noch Elemente? => Diese Werte kopieren

Diese drei Punkte kann man doch etwas sehen als ein "Minimum finden von den Listen, die noch Werte haben."

Wie man dies darstellt ist Dir überlassen. Man kann natürlich mehrere Listen haben. Aber wenn man alles einfacher in einer Liste halten möchte, dann ginge dies auch. Man hat dann halt sowas wie Start und End-Element. Das wäre dann ähnlich wie bei dem ganzen mergesort: Dir wird ja immer ein ganzes gegeben, aber da hast Du dann Anfang und Ende, das den Rahmen betrachtet, der dann verwendet wird.
Die Gestaltungsmöglichkeiten sind hier recht hoch.
Nur eben musst Du in irgend einer Weise die Daten halten und da würde sich aus meiner Sicht ein Array anbieten, denn die Anzahl der Teil-Listen kennen wir ja, oder?
 
Gut das verstehe ich. Vielen Dank. Die technische Umsetzung bereitet mir Probleme. Ich rufe
merge (a, low, high, x); auf, d.h ich verwalte eine Liste der Größe high-low+1. Das Problem ist, dass ich ja jetzt nicht wieder einen leftindex rightindex habe, sondern vllt auch viel mehr. Wie kann ich also jetzt diese einen Liste verwalten?
 
Moment - die Parameter (a, low, high, x) waren doch die Parameter vom mergesort und nicht vom merge,

Der klassische merge Aufruf hat die Teillisten als Input bekommen und hat dann eine neue Liste mit allen Elementen zurück gegeben. (So man nach https://de.wikipedia.org/wiki/Mergesort schaut. Da ist das so gezeigt.) Aber Du kannst mir gerne kurz zeigen, wie es bisher implementiert wurde von euch.

Daher einfach einmal genau schauen, wie das derzeit bei x = 2 implementiert ist und dann erweitern.
 
public static void mergesort (List<T> a, int low, int high, int x) { if (low < high) { for (int i = 0; i < x; i++) { mergesort (a,low + i*(high-low+1)/x, low + (i+1)*(high-low+1)/x - 1,x); } merge (a, low, high, x); }
Dann ist das doch falsch am Ende:

Wir haben gar niichts implementiert. Das müssen wir alles selber hinbekommen oder was meinst du genau?

Ich kann mich nur an meiner eigen Methode merge für x=2 orientieren
 
Also wenn man immer nur Ausschnitte sieht, dann ist es schwer, immer alles sofort richtig zu sehen.

Also Fakt ist: An Deinem Code für x=2 solltest Du Dich orientieren. Den Code kenne ich aber nicht (Evtl. macht es Sinn, diesen auch einmal kurz zu zeigen).

Die Parameter vom merge muss man für sich definieren. Auch das Verhalten intern und nach außen sind wichtig. Wo werden die Listen erzeugt, die notwendig sind. Soll die Ursprungsliste angepasst werden? u.s.w.

Was die konkreten Argumente vom merge angeht, so werden hier die Teillisten benötigt. Wenn mergesort die original Liste anpasst und ändert (Returncode void besagt das ja schon), dann ist klar, dass nach dem Aufruf von mergesort die teilsortierten Listen in der original Liste enthalten sind.
Die Grenzen dieser Liste konntest Du aber bestimmen, denn diese stecken ja auch in der for Schleife. Somit ist tatsächlich die Übergabe von der Liste, dem Start und Ende Wert und der Anzahl der Listen (x) ausreichend um erneut die Listengrenzen zu bestimmen.
Somit war es ein Denkfehler von mir, dass die Argumente so nicht passen würden. Sie können durchaus passen.
 
Java:
private static <T extends Comparable<? super T>> void merge(List<T> a, int p, int q, int r) {
        
        int half=q-p+1;
        int otherhalf=r-q;
        //kopieren, 2 Teilarrays
        List<T> left=new ArrayList<T>();
        List<T> right=new ArrayList<T>();
        
        for(int i=0; i<half;i++) {
            left.add(i,a.get(p+i));
        }
        for(int i=0; i<otherhalf;i++) {
            right.add(i,a.get(q+i+1));
        }
        
        int leftindex,rightindex,resultindex;
        leftindex=rightindex=0;
        resultindex=p;
        
            
            //beide Arrays haben Elemente
            while(leftindex<left.size() && rightindex<right.size()) {
                
                //beide Arrays enthalten Elemente
                if(left.get(leftindex).compareTo(right.get(rightindex))<0) {
                    
                    a.set(resultindex,left.get(leftindex));
                    resultindex++;
                    leftindex++;
                }
                else {
                    a.set(resultindex,right.get(rightindex));
                    resultindex++;
                    rightindex++;
                }
            }
            //linkes enthält Elemente
        while(leftindex< left.size()) {
                a.set(resultindex,left.get(leftindex));
                resultindex++;
                leftindex++;
            }
            //rechtes enthält Elemente
            while(rightindex< right.size()) {
                a.set(resultindex,right.get(rightindex));
                resultindex++;
                rightindex++;
                
            }   
        }
Das ist der code.
Ich kann also meine Listengröße aus high-low+1 bestimmen, aber wie teile ich diese nun auf. Für x=2 ist das klar, aber ich kann es mir im Allgemeinen noch nicht vorstellen. Ich denke mir immer, dass ich dann auch x Listen brauche, aber das kann ja nicht sein. vor allem müsste ich nicht, wie ich sowas realsieren kann?
 
Doch, nach meinem Verständnis brauchst Du (bis zu) x Listen (Es sei denn, Du hast weniger Felder, dann brauchst Du nur so viele Listen wie Du Felder hast).

Du weisst, wie viele Listen Du brauchst, d.h. Du kannst ein Array von Listen erzeugen und diese Füllen. Im rekursiven Aufruf hast Du ja schon die Grenzen gehabt. Also in etwa wie folgt (Nicht 100% Java - aber ich habe etwas versucht, mich an die Java Syntax zu halten):
Java:
List<T>[] listen = new List<T>[](x);
for (int i = 0; i < x; i++) { 
//    mergesort (a,low + i*(high-low+1)/x, low + (i+1)*(high-low+1)/x - 1,x); 
//    Grenzen erste Liste sind: low + i*(high-low+1)/x  und low + (i+1)*(high-low+1)/x - 1
    listen[i] = new List<T>();
    for (int j=low + i*(high-low+1)/x; i<= low + (i+1)*(high-low+1)/x - 1; j++)
        listen[i].add(a.get(j));
}
Wie du siehst: Ich habe Deinen original Code vom rekursiven Aufruf einmal drin gelassen und die Grenzen als Kommentar dazu geschrieben.
Und da legst Du dann die Listen an. Ebenso kannst Du dann auch ein array von Integern erstellen, die dann anzeigen, wie weit Du durch jede Liste durch bist. Und schon kannst Du in einer Schleife durch die Listen gehen um zu schauen, welche Liste das Minimum enthält....

Das wäre so meine Idee um das etwas zu lösen.
 
Aha. Vielen Dank. Das mit dem Array ist ja genial.
Also ich lege mir dann das Interger-Array b als Verwaltung für meine Listen an. Dann suche ich mir immer nur das min von den noch vollen Listen.d.h es muss gelten b <listen.size().
Ich verstehe nur nicht deine Verschachtelung in der for Schleife. Ich hätte gedacht in mergesort wird doch erst merge aufgerufen nachdem die for schleife abgearbeitet wurde.
 
Passende Stellenanzeigen aus deiner Region:

Oben