MergeSort allgemein

Bitte aktiviere JavaScript!
A

Anzeige


Vielleicht hilft dir dieser Kurs hier weiter: (hier klicken)
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?
 
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.
 
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.
 
@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?
 
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...
 
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?
 
Hier schau mal:
Java:
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++;
       }
    }
 
Das ist nicht der komplette Code. Ich meine wirklich vollständig, so dass man das Teil übersetzen und ausführen kann.
 
Tut mir leid.
Hier:
Java:
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);

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

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

    }
}
 
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.
 
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. o_O
 
@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).
 
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:)
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 :)
 
Passende Stellenanzeigen aus deiner Region:

Neue Themen

Oben