MergeSort allgemein

LeonInfo19

Bekanntes Mitglied
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?
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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?
 
K

kneitzel

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

Blender3D

Top Contributor
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.
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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.?
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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?
 
K

kneitzel

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

LeonInfo19

Bekanntes Mitglied
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
 
K

kneitzel

Gast
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

Bekanntes Mitglied
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?
 
K

kneitzel

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

LeonInfo19

Bekanntes Mitglied
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.
 
K

kneitzel

Gast
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

Top Contributor
Er meint so etwas (Achtung: hier ist high exclusive):
Java:
    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

Bekanntes Mitglied
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

Bekanntes Mitglied
Wie erstelle ich den im Code ein Array von Listen:
Java:
    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?
 
K

kneitzel

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

Bekanntes Mitglied
Vielen Dank.
Aber dann würde doch folgendes passen:
Java:
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

Top Contributor
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....
 
K

kneitzel

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

kneitzel

Gast
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

Bekanntes Mitglied
Ich habe jetzt mal versucht, die merge Methode fertigzustellen.
Java:
    //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.
 
K

kneitzel

Gast
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

Bekanntes Mitglied
Wenn ich das Programm mit einem Integer-Array teste, bekomme ich eine ClasscastException.
Java:
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:
Java:
  List<T>[] listen = (List<T>[]) new Object[t];

Wie kann ich das beheben?
 

LeonInfo19

Bekanntes Mitglied
Ok das hat geklappt. Das mit dem min nicht:
Java:
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

Top Contributor
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

Bekanntes Mitglied
Meinst du es so:
Java:
 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++;
       }
 
Zuletzt bearbeitet:

LeonInfo19

Bekanntes Mitglied
Danke. Trotzdem funktioniert das nicht.
Folgendes Bsp:
Java:
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?
 
K

kneitzel

Gast
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

Top Contributor
Die Zeile
Java:
if(lists[i].size()<size[i] ) {//lists[i] has elements
verstehe ich nicht. Da hätte ich
Java:
if(index[i] < lists[i].size()) {//lists[i] has elements
erwartet.
 

LeonInfo19

Bekanntes Mitglied
@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

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

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

Bekanntes Mitglied
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?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Devin Mergesort verstehen Allgemeine Java-Themen 3
Kirby.exe K-Way MergeSort Allgemeine Java-Themen 33
J Rekursion Mergesort Allgemeine Java-Themen 10
U Methoden Algorithmus MergeSort String [ ] array sortieren programmieren Allgemeine Java-Themen 17
X MergeSort Laufzeit Problem Allgemeine Java-Themen 4
T Threads Mergesort mit limitierter Threadanzahl Allgemeine Java-Themen 2
S MergeSort iterativ und rekursiv? Allgemeine Java-Themen 8
B Generische Datentypen MergeSort Allgemeine Java-Themen 5
B Hilfe beim Verständnis von Mergesort Allgemeine Java-Themen 5
R MergeSort funktioniert nicht Allgemeine Java-Themen 5
D MergeSort Allgemeine Java-Themen 19
H [LinkedList] Sortieren durch MergeSort Allgemeine Java-Themen 3
N externes Sortieren (MergeSort Allgemeine Java-Themen 2
D Chat GPT allgemein und in Bezug auf Softwareentwicklung Allgemeine Java-Themen 105
L allgemein Strings händisch in Liste sortieren Allgemeine Java-Themen 47
K Best Practice JFrame Objekt allgemein zugänglich machen Allgemeine Java-Themen 8
chuxXo BasicPlayer - Beendigung Abfragen (Allgemein) Allgemeine Java-Themen 21
J Allgemein gültige Klasse/Methode mehrfach verwenden Allgemeine Java-Themen 11
F Huffman Allgemein Allgemeine Java-Themen 1
G allgemein synchroniszed verständnisfrage Allgemeine Java-Themen 19
J Client Allgemein Allgemeine Java-Themen 10
M Frage zum Design :: allgemein Allgemeine Java-Themen 6
S Frage zu jTDS, JAVA allgemein und Timer Allgemeine Java-Themen 6

Ähnliche Java Themen

Neue Themen


Oben