# MergeSort allgemein



## LeonInfo19 (2. Mai 2019)

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.

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


----------



## kneitzel (2. Mai 2019)

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.


----------



## LeonInfo19 (2. Mai 2019)

kneitzel hat gesagt.:


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


----------



## kneitzel (2. Mai 2019)

LeonInfo19 hat gesagt.:


> 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.


----------



## LeonInfo19 (2. Mai 2019)

Danke. Das habe ich jetzt verstanden


kneitzel hat gesagt.:


> 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.


Wie kann ich denn sowas realisieren?
Dieser Teil muss ja in der mergesort-Methode gemacht werden.


----------



## LeonInfo19 (2. Mai 2019)

kneitzel hat gesagt.:


> Ist x > n= Dann: n Aufrufe mit nur einem Element.


EIn Element ist doch sortiert. Muss da nicht dann die Methode abrechen?


----------



## Blender3D (2. Mai 2019)

LeonInfo19 hat gesagt.:


> 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.


----------



## kneitzel (2. Mai 2019)

LeonInfo19 hat gesagt.:


> 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").



Blender3D hat gesagt.:


> 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_:
> 
> ...



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  )


----------



## LeonInfo19 (2. Mai 2019)

```
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


----------



## kneitzel (2. Mai 2019)

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!)


----------



## LeonInfo19 (2. Mai 2019)

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


----------



## kneitzel (3. Mai 2019)

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?


----------



## LeonInfo19 (3. Mai 2019)

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?


----------



## kneitzel (3. Mai 2019)

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.


----------



## mihe7 (3. Mai 2019)

LeonInfo19 hat gesagt.:


> Ich bin nicht ganz sicher.


Das lässt sich durch Nachrechnen schnell ändern.

Nimm z. B. high = 9, low = 0, x = 4 an. Dann ist (high - low + 1) / 4 = 10 / 4 = 2. Deine berechneten low-Indizes in der Schleife sind dann: 0, 2, 4, 6, die high-Indizes sind jeweils eins höher -> da fehlt was.


----------



## LeonInfo19 (3. Mai 2019)

LeonInfo19 hat gesagt.:


> 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


----------



## kneitzel (3. Mai 2019)

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.


----------



## LeonInfo19 (3. Mai 2019)

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


----------



## kneitzel (3. Mai 2019)

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

```
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.


----------



## LeonInfo19 (3. Mai 2019)

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._


----------



## kneitzel (3. Mai 2019)

LeonInfo19 hat gesagt.:


> _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._


Ja, das ist eine andere Schleife. Die Schleife in mergesort bleibt auch so, wie sie ist. Auch den Aufruf von merge kannst Du so lassen.

Das war eine erste Schleife in merge, um die Listen, die du mergen musst, zu füllen.


----------



## mihe7 (3. Mai 2019)

Er meint so etwas (Achtung: hier ist high exclusive):

```
private static <T extends Comparable<T>> void merge(
             List<T> list, int low, int high, int x) {
        int[] ix = new int[x];
        int n = high - low;
        for (int i = 0; i < x; i++) {
            ix[i] = low + (n/x)*i;
        }
        ...
```


----------



## LeonInfo19 (3. Mai 2019)

Sorry ich hatte Vorlesung. Danke für eure Beiträge.
D.h ich muss also jetzt nur noch in einer Schleife über die  Listen und über mein Zahlen Array laufen. In jeder Stufe muss ich dann überpüfen ob es schon leere Listen gibt. Von dem restlichen Suche ich dann das min.
Ich könnte dann wieder mit meinem resultindex arbeiten, um mein merge-array zu verwalten.


----------



## LeonInfo19 (3. Mai 2019)

mihe7 hat gesagt.:


> Nimm z. B. high = 9, low = 0, x = 4 an. Dann ist (high - low + 1) / 4 = 10 / 4 = 2. Deine berechneten low-Indizes in der Schleife sind dann: 0, 2, 4, 6, die high-Indizes sind jeweils eins höher -> da fehlt was.


@mihe7 
Sorry ich habe das übersehen. Aber warum sollte etwas fehlen. Der high index geht doch bis 7?


----------



## mihe7 (3. Mai 2019)

high == 9 nicht high == 7


----------



## LeonInfo19 (3. Mai 2019)

Oh ja. Dann muss ich einfach die Schleife bis einschließlich x laufen lassen oder?


----------



## LeonInfo19 (3. Mai 2019)

Wie erstelle ich den im Code ein Array von Listen:

```
List<T>[] listen = new  List<T>[]();
```
Das geht ja nicht.
Aber ein Array von generischen Typen kann ich gar nicht erstellen. Gibt es da einen Ausweg?


----------



## kneitzel (3. Mai 2019)

Ja, da gibt es mehrere Auswege. Ein Ausweg ist, Array.newInstance() zu nutzen. Damit kann man zur Laufzeit sowas anlegen.

Aber der Weg, der z.B. auch im Buch EffectiveJava empfohlen wird, ist einfach nur die Nutzungs einer Object[] welches dann da rein gecastet wird. Also ein Beispiel-Code wäre:

```
import java.util.*;

public class GenericTest<T extends Comparable<T>> {

    public void test() {
        List<T>[] testArray = (List<T>[]) new Object[5];
        for (int i=0; i<5; i++)
            testArray[i] = new ArrayList<T>();
    }

    public static void main (String[] args) {
        GenericTest<Integer> instance = new GenericTest<>();
        instance.test();
    }
}
```

Sprich: In der Funktion erstellst Du ein Array aus Object Objekten und castest die zu deinem gewünschten Typ. Und dann füllst Du dieses Array einfach entsprechend.


----------



## LeonInfo19 (3. Mai 2019)

Vielen Dank.
Aber dann würde doch folgendes passen:

```
List<T>[] listen = (List<T>[]) new Object[x];
        for (int i = 0; i < x; i++) {
            listen[i] = new ArrayList<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));
```


----------



## mihe7 (3. Mai 2019)

LeonInfo19 hat gesagt.:


> Oh ja. Dann muss ich einfach die Schleife bis einschließlich x laufen lassen oder?



Wenn Du 10 Elemente in vier Listen teilen willst, dann könntest Du z. B. 3 x 2 + 1 x 4 draus machen, sprich: den letzten Index auf high setzen. Man könnte aufrunden, dann wären es - in diesem Fall - 3 x 3 + 1 x 1. Bei 9 Elementen hättest Du dann aber das Problem, dass eine Liste leer wäre. Kann grad nicht denken....


----------



## kneitzel (3. Mai 2019)

Sieht erst einmal gut aus. Hast Du es mal getestet, ob er die Arrays wie gewünscht aufteilt? Ich muss gestehen, dass ich es auch ohne durchspielen nicht auf Anhieb sehe, ob es richtig ist. Aber so in der Art hatte ich mir das tatsächlich vorgestellt.

@mihe7: Die Aufteilung ging ganz gut. Das hatten wir ja schon im ersten Teil, der mergesort Funktion.


----------



## mihe7 (3. Mai 2019)

kneitzel hat gesagt.:


> Die Aufteilung ging ganz gut. Das hatten wir ja schon im ersten Teil, der mergesort Funktion.


Ja, das bezieht sich auch noch auf den ersten Teil (s. Kommentar #15)


----------



## kneitzel (3. Mai 2019)

Ach jee ... Stimmt.... Aber ich hatte es mal an einem Beispiel durchgerechnet und da ging es irgendwie auf. Evtl. gibt es Kombinationen, bei denen es aufgeht und ich habe prompt so eine gefunden 

Und da ist deine Idee doch recht gut, denn die versteht man sofort. Alle Felder sind gleich groß, nur das Letzte, das bekommt den ganzen Rest. So hat man weniger Probleme mit einem Denkfehler (Wobei man diese Logik ja so oder so in einem Unit Test abdecken würde, so dass diese Gefahr wohl auch nicht ganz so groß ist. Aber man verschwendet ggf. viel Zeit...)

Dann müsste man aber auch den Fall abfangen, dass n < x ist. Also das zu sortierende Feld hat 3 Elemente und ich will mit x=5 rechnen. 3/5 = 0, also habe ich 4 mal ein Feld Größe 0 (fein, nichts zu tun) und dann den Aufruf für die ganzen Felder .... was dann eine Endlosschleife werden dürfte bis eben ein Stack overflow auftritt.


----------



## LeonInfo19 (3. Mai 2019)

Ich habe jetzt mal versucht, die merge Methode fertigzustellen.

```
//Größenverwaltung der Listen
          
        int[] groeße = new int[t];
        int n = high - low;
        for (int i = 0; i < t; i++) {
            groeße[i] = low + (n/t)*i;
        }
       
        int resultindex=0;
        T min =null;
        int j=0;
     
        while(resultindex<high-low+1) {
         
            for(int i=0; i<t;i++) {
                if(listen[i].size()<groeße[i] ) {
                    if(min.compareTo(listen[i].get(j))<0) {
                        min=listen[i].get(j);
                    }
               }
            }
        j++;
        a.set(resultindex,min);
        resultindex++;
        }
```

Die Frage ist, ob das mit dem min so geht. Wsl muss das anders initialisiert werden.


----------



## kneitzel (3. Mai 2019)

Also ich habe es jetzt nicht durchgespielt, aber es sieht erst mal danach aus, was ich mir so vorgestellt hatte.

Du musst aber meiner Meinung nach abfangen, ob min null ist. Also noch ein min==null davor. Die Bedingung wird also zu sowas wie: *min==null || min.compareTo(listen......)*


----------



## LeonInfo19 (3. Mai 2019)

Ok gut. Ich habe mich nur gefragt, ob der 1.Vergleich funktioniert, da ja min mit null initialisiert ist.


----------



## LeonInfo19 (3. Mai 2019)

Wenn ich das Programm mit einem Integer-Array teste, bekomme ich eine ClasscastException.

```
private static <T extends Comparable<? super T>> void merge (List<T> a, int low, int high, int t) {
        
        List<T>[] listen = (List<T>[]) new Object[t]; //geht wsl hier doch nicht so?
        for (int i = 0; i < t; i++) {
       
            listen[i] = new ArrayList<T>();
            for (int j=low + i*(high-low+1)/t; i<= low + (i+1)*(high-low+1)/t - 1; j++)
                listen[i].add(a.get(j));
        }
         //Größenverwaltung der Listen
          
        int[] groeße = new int[t];
        int n = high - low;
        for (int i = 0; i < t; i++) {
            groeße[i] = low + (n/t)*i;
        }
        
        int resultindex=0;
        T min =null;
        int j=0;
        
        while(resultindex<high-low+1) {
            
            for(int i=0; i<t;i++) {
            if(listen[i].size()<groeße[i] ) {
                if(min.compareTo(listen[i].get(j))<0) {
                    min=listen[i].get(j);
                }
            }
        }
        j++;
        a.set(resultindex,min);
        resultindex++;
       }
```

Es liegt wsl an der Zeile mit dem cast: 
	
	
	
	





```
List<T>[] listen = (List<T>[]) new Object[t];
```

Wie kann ich das beheben?


----------



## LeonInfo19 (3. Mai 2019)

Ok das hat geklappt. Das mit dem min nicht:

```
int resultindex=0; //index for for List<T> a
        T min =null;
        int j=0;
         while(resultindex<high-low+1) {
            
            for(int i=0; i<t;i++) {
                if(lists[i].size()<size[i] ) {//lists[i] has elements
                    if(min==null || min.compareTo(lists[i].get(j))<0) {
                        min=lists[i].get(j);
                        }
                    }
                }
            j++;
            a.set(resultindex,min);
            resultindex++;
       }
```

Ich laufe hier   if(min==null || min.compareTo(lists_.get(j))<0)  aus dem Index des Arrays, weil j damit beliebig groß werden kann. Wenn ich jedoch (min!=null && min.compareTo(lists.get(j))<0) versuche, bekomme ich ein Array aus null. Wie löse ich das?_


----------



## mihe7 (4. Mai 2019)

Das j ist von der jeweiligen Liste abhängig -> Du brauchst ein Array von Indizes - für jede Liste einen Index. Außerdem musst Du Dir in der for-Schleife merken, welche Liste das Minimum enthält, damit Du den richtigen Index erhöhen kannst.


----------



## LeonInfo19 (4. Mai 2019)

Meinst du es so:

```
int indexmin=0;
        int index []=new int[t];
         while(resultindex<high-low+1) {
            
            for(int i=0; i<t;i++) {
                if(lists[i].size()<size[i] ) {//lists[i] has elements 
                    if(min==null || min.compareTo(lists[i].get(index[i]))<0) {
                        min=lists[i].get(index[i]);
                        indexmin=i;
                        }
                    }
                }
            index[indexmin]+=1;
            
            a.set(resultindex,min);
            resultindex++;
       }
```


----------



## mihe7 (4. Mai 2019)

LeonInfo19 hat gesagt.:


> Meinst du es so:


Ja.


----------



## LeonInfo19 (4. Mai 2019)

Danke. Trotzdem funktioniert das nicht.
Folgendes Bsp:

```
public static void main(String [] args) {
        
        ArrayList a=new ArrayList();
        a.add(2);
        a.add(4);
        a.add(1);
        a.add(5);
        a.add(3);
        setT(3);
        System.out.println(a);
        sort(a);
        System.out.println(a);
```

Ich bekomme eine IndexOutOfBoundsException in der Zeile mit     min=lists_.get(index);
Warum?_


----------



## kneitzel (4. Mai 2019)

Kannst Du uns den aktuellen Code einmal zeigen? Sonst wird es schwer, hierzu etwas zu sagen.
Aber ich meine, dass die Prüfung, ob in einer liste noch werte zum auslesen sind, nicht ganz richtig ist bzw fehlt. Aber ich habe auch nur den Code aus Antwort 38.


----------



## mihe7 (4. Mai 2019)

Die Zeile 

```
if(lists[i].size()<size[i] ) {//lists[i] has elements
```
verstehe ich nicht. Da hätte ich

```
if(index[i] < lists[i].size()) {//lists[i] has elements
```
erwartet.


----------



## LeonInfo19 (4. Mai 2019)

@mihe7: Ich konnte dich leider nicht zum Gespräch einladen. Da Programm läuft jetzt, jedoch mit dem falschen Ergebnis:
[2, 4, 1, 5, 3]
[5, 5, 5, 5, 5]
D.h er nimmt wohl immer das max. Der Fehler liegt also immer noch in der while-Schleife. Weist du wo?


----------



## mihe7 (4. Mai 2019)

LeonInfo19 hat gesagt.:


> Weist du wo?


Ja. Sorry, ich hatte mir Deinen Code nicht so genau angesehen.


```
if(min==null || min.compareTo(lists[i].get(index[i]))<0) {
                        min=lists[i].get(index[i]);
```
bedeutet ja, wenn min < Listenelement, dann ersetze min durch das Listenlement. Das ist natürlich Unsinn. Der Vergleich muss genau umgekehrt sein (>): wenn min > Listenelement, dann gibt es ein Listelement, das kleiner als min ist...


----------



## LeonInfo19 (4. Mai 2019)

Ja stimmt.Trotzdem funktioniert es dann leider immer noch nicht: Ergebnis ist dann::
[2, 4, 1, 5, 3]
[3, 3, 3, 3, 3]
Weist du da nochmals Rat?


----------



## mihe7 (4. Mai 2019)

vor der for-Schleife musst Du das min zurücksetzen (min = null), sonst bringt das nichts


----------



## LeonInfo19 (4. Mai 2019)

Ja  Aber leider wieder nicht:
[2, 4, 1, 5, 3]
[3, 5, 1, 5, 3]


----------



## mihe7 (4. Mai 2019)

Poste mal Deinen kompletten Code, bitte.


----------



## LeonInfo19 (4. Mai 2019)

Hier schau mal:

```
public static <T extends Comparable<? super T> > void sort(List<T> array) {
        
        
        mergesort (array, 0, array.size() - 1, t);
    }
    
    private static <T extends Comparable<? super T>> void mergesort (List<T> a, int low, int high, int t) {
        if (low < high) {
            for (int i = 0; i < t; i++) {
                mergesort (a,low + i*(high-low+1)/t, low + (i+1)*(high-low+1)/t - 1,t);
            }
            merge (a, low, high, t);
        }

    }

    private static <T extends Comparable<? super T>> void merge (List<T> a, int low, int high, int t) {
        
        List<T>[] lists = (List<T>[]) new List<?>[t];
        for (int i = 0; i < t; i++) {
            lists[i] = new ArrayList<T>();
            for (int j=low + i*(high-low+1)/t; j<= low + (i+1)*(high-low+1)/t - 1; j++)
                lists[i].add(a.get(j));
        }
        
        int[] size = new int[t];
        int n = high - low;
        for (int i = 0; i < t; i++) {
            size[i] = low + (n/t)*i;
        }
        
        int resultindex=0;
        T min =null;
        
        int indexmin=0;
        int index []=new int[t];
        while(resultindex<high-low+1) {
            min=null;
            for(int i=0; i<t;i++) {
                if(index[i] < lists[i].size()){
                    if(min==null || min.compareTo(lists[i].get(index[i]))>0) {
                        min=lists[i].get(index[i]);
                        indexmin=i;
                        }
                    }
                }
            index[indexmin]+=1;
            
            a.set(resultindex,min);
            resultindex++;
       }
    }
```


----------



## mihe7 (4. Mai 2019)

Das ist nicht der komplette Code. Ich meine wirklich vollständig, so dass man das Teil übersetzen und ausführen kann.


----------



## LeonInfo19 (4. Mai 2019)

Tut mir leid.
Hier:

```
import java.util.*;
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> array) {
        
        
        mergesort (array, 0, array.size() - 1, t);
    }
    
    private static <T extends Comparable<? super T>> void mergesort (List<T> a, int low, int high, int t) {
        if (low < high) {
            for (int i = 0; i < t; i++) {
                mergesort (a,low + i*(high-low+1)/t, low + (i+1)*(high-low+1)/t - 1,t);
            }
            merge (a, low, high, t);
        }

    }

    private static <T extends Comparable<? super T>> void merge (List<T> a, int low, int high, int t) {
        
        List<T>[] lists = (List<T>[]) new List<?>[t];
        for (int i = 0; i < t; i++) {
            lists[i] = new ArrayList<T>();
            for (int j=low + i*(high-low+1)/t; j<= low + (i+1)*(high-low+1)/t - 1; j++)
                lists[i].add(a.get(j));
        }
        
        int[] size = new int[t];
        int n = high - low;
        for (int i = 0; i < t; i++) {
            size[i] = low + (n/t)*i;
        }
        
        int resultindex=0;
        T min =null;
        
        int indexmin=0;
        int index []=new int[t];
        while(resultindex<high-low+1) {
            min=null;
            for(int i=0; i<t;i++) {
                if(index[i] < lists[i].size()){
                    if(min==null || min.compareTo(lists[i].get(index[i]))>0) {
                        min=lists[i].get(index[i]);
                        indexmin=i;
                        }
                    }
                }
            index[indexmin]+=1;
            
            a.set(resultindex,min);
            resultindex++;
       }
    }
    public static void main(String [] args) {
        
        ArrayList a=new ArrayList();
        a.add(2);
        a.add(4);
        a.add(1);
        a.add(5);
        a.add(3);
        setT(3);
        System.out.println(a);
        sort(a);
        System.out.println(a);

    }
}
```


----------



## mihe7 (4. Mai 2019)

Wie ich schon mehrfach geschrieben habe, ist die Aufteilung falsch. Dann muss beim Setzen des Ergebnisses low zum resultindex addiert werden. Hab das mal geändert:


```
import java.util.*;
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> array) {
        
        
        mergesort (array, 0, array.size(), t);
    }

    private static <T extends Comparable<? super T>> void mergesort (List<T> a, int low, int high, int t) {       
        int size = high - low;
        int step = (size + t - 1) / t;
        if (size > 1 && step > 0) {
            for (int i = 0; i < t; i++) {
                int l = Math.min(low + i*step, high);
                int h = Math.min(low + (i+1)*step, high);
                mergesort (a, l, h, t);
            }
            merge (a, low, high, t);
        }
    }

    private static <T extends Comparable<? super T>> void merge (List<T> a, int low, int high, int t) {
        int size = high - low;
        int step = (size + t - 1) / t;
        List<T>[] lists = (List<T>[]) new List<?>[t];
        for (int i = 0; i < t; i++) {
            int l = Math.min(low + i*step, high);
            int h = Math.min(low + (i+1)*step, high);
            lists[i] = new ArrayList<T>(a.subList(l, h));
        }
        
        int resultindex=0;
        T min =null;
        
        int indexmin=0;
        int index []=new int[t];
        while(resultindex<size) {
            min=null;
            for(int i=0; i<t;i++) {
                if(index[i] < lists[i].size()){
                    if(min==null || min.compareTo(lists[i].get(index[i]))>0) {
                        min=lists[i].get(index[i]);
                        indexmin=i;
                    }
                }
            }
            index[indexmin]+=1;
            
            a.set(low+resultindex,min);
            resultindex++;
        }
    }
    public static void main(String [] args) {
        
        ArrayList a=new ArrayList();
        a.add(2);
        a.add(4);
        a.add(1);
        a.add(5);
        a.add(3);
        setT(3);
        System.out.println(a);
        sort(a);
        System.out.println(a);

    }
}
```


----------



## LeonInfo19 (4. Mai 2019)

Vielen Dank für deine Hilfe


mihe7 hat gesagt.:


> int step = (size + t - 1) / t;


Warum hast du step so gewählt?


----------



## mihe7 (5. Mai 2019)

Zum Aufrunden. Nimm mal den Fall an, dass size < t gilt, dann würde step = size/t dazu führen, dass step == 0 gilt. Gar nicht gut.


----------



## Blender3D (5. Mai 2019)

mihe7 hat gesagt.:


> private static <T extends Comparable<? super T>> void merge (List<T> a, int low, int high, *int t*)


Also abgesehen davon, dass ich in dem Ansatz einen beliebigen Teiler statt* 2* für mergeSort zu verwenden, keinen Sinn außer unnötigen Mehraufwand sehe. (Siehe Post #7)
Warum wird hier *t *übergeben. Der Parameter ist als Klassenvariable vorhanden und wird unnötigerweise durchgereicht.


----------



## mihe7 (5. Mai 2019)

@Blender3D bzgl. der Übergabe von t reiche ich die Frage mal an @LeonInfo19 weiter; ich habe an seinem Code nur das Nötigste verändert 

Was t > 2 betrifft, so vermute ich da einfach mal eine entsprechende Aufgabenstellung dahinter. Praktisch würde das in meinen Augen in erster Linie Sinn bei externem Sortieren machen (dann aber natürlich etwas anders implementiert).


----------



## LeonInfo19 (5. Mai 2019)

mihe7 hat gesagt.:


> Zum Aufrunden. Nimm mal den Fall an, dass size < t gilt, dann würde step = size/t dazu führen, dass step == 0 gilt. Gar nicht gut.


Alles klar


Blender3D hat gesagt.:


> Also abgesehen davon, dass ich in dem Ansatz einen beliebigen Teiler statt* 2* für mergeSort zu verwenden, keinen Sinn außer unnötigen Mehraufwand sehe. (Siehe Post #7)
> Warum wird hier *t *übergeben. Der Parameter ist als Klassenvariable vorhanden und wird unnötigerweise durchgereicht


Ja das t>2 lag an der Aufgabenstellung.
Ja das t im Methodenkopf ist unnötig. Ich habe die setT methode erst gegen Ende hinzugefügt. Deshalb habe ich das nicht mehr geändert. Danke für den Hinweis


----------



## LeonInfo19 (8. Mai 2019)

Hallo,
ich wollte mich nochmal bei euch 3 herzlich für euere Unterstützung bedanken.
Vielen Dank mihe7, kneitzel und Blender3D


----------



## mihe7 (8. Mai 2019)

Das ist aber nett von Dir. Hat es am Ende wenigstens was gebracht?


----------



## LeonInfo19 (8. Mai 2019)

Ja sehr viel. Ich habe dadurch auch die Rekurion nochmals beser verstanden.
Vielen Dank


----------

