MergeSort allgemein

Bitte aktiviere JavaScript!
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.
 
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;
        }
        ...
 
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.
 
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?
 
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.
 
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));
 
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....
 
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.
 
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.
 
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.
 
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......)
 
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?
 
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?
 
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.
 
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:
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben