MergeSort allgemein

LeonInfo19

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

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

LeonInfo19

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

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

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

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

Top Contributor
@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).
 

LeonInfo19

Bekanntes Mitglied
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 :)
 
Ä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