MergeSort allgemein

[LeonInfo19]

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]

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]

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]

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]

Danke. Das habe ich jetzt verstanden

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]

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

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

 

[Blender3D]

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]

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 )

 

[LeonInfo19]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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]

high == 9 nicht high == 7

 

[LeonInfo19]

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

 

[LeonInfo19]

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]

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]

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]

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]

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]

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]

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]

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]

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]

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

 

[LeonInfo19]

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]

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]

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]

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]

Meinst du es so:

Ja.

 

[LeonInfo19]

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]

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]

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]

@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]

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]

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]

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

 

[LeonInfo19]

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

 

[mihe7]

Poste mal Deinen kompletten Code, bitte.