MergeSort allgemein

Diskutiere MergeSort allgemein im Allgemeine Java-Themen Bereich.
L

LeonInfo19

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

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

mihe7

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

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

mihe7

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

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

mihe7

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

LeonInfo19

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++;
       }
    }
 
mihe7

mihe7

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

LeonInfo19

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

    }
}
 
mihe7

mihe7

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

    }
}
 
mihe7

mihe7

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

Blender3D

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
 
mihe7

mihe7

@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).
 
L

LeonInfo19

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

LeonInfo19

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

MergeSort allgemein

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben