Quicksort

Diskutiere Quicksort im Allgemeine Java-Themen Bereich.
Kirby_Sike

Kirby_Sike

Also wir hatte die Aufgabe einen Quicksort Algorithmus zu schreiben, jedoch bin ich gerade confused...xD Ich bin in dem sinne confused, dass ich nicht ganz nachvollziehen kann wie wir das Pivot Element wählen sollen xD Ich habe es einfach mit Random für die jeweilige Partitions Range gemacht. Dies ist jedoch scheinbar falsch xD Ich schicke einfach mal die Aufgaben Stellung :)

Bildschirmfoto 2020-06-01 um 08.24.05.png

Was mich an dem Median confused ist, wie sie es gerne hätten xD Soll ich mir einfach drei Indices generieren und davon den Median nehmen oder wie soll ich das tuen xD ?

Hier ist meine aktuelle getPivot-Methode:

Java:
private static int getPivot(int low, int high) {
    Random r = new Random();
    return r.nextInt((high-low)+1) + low;
}
 
Kirby_Sike

Kirby_Sike

Also soweit ich das verstanden habe, ist es eine gängige Methode das erste, das mittlere und das letzte Element der Liste zu nehmen und davon den Median zu bilden. Jedoch stell sich da trotzdem noch fragen meinerseits xD

Wie bilde ich den Median bei generischen Typen (denn soweit ich es noch aus der Schule in Erinnerung habe, ist der Median bei einer ungeraden Anzahl an Elementen immer das mittlere Element) xD Sollte das richtig sein, verstehe ich den nutzen davon nicht, da es ja dann äquivalent zu dem ist, was meine getPivot() Methode tut. Oder etwa nicht? xD
 
Kirby_Sike

Kirby_Sike

Na gut dann nevermind xD Dann werde ich voll die Elemente mit comparable vergleichen müssen und aufsteigend sortieren xD
 
Kirby_Sike

Kirby_Sike

Also das ist nicht sonderlich effizient, jedoch funktioniert es hiermit xD Ich versuche es mal etwas zu optimieren :)

Java:
public static <T extends Comparable<? super T> > int pivot(List<T> list, int low, int high) {
        Random r = new Random();
        ArrayList<T> arr = new ArrayList<>();
        arr.add(list.get(r.nextInt((high-low)+1) + low));
        arr.add(list.get(r.nextInt((high-low)+1) + low));
        arr.add(list.get(r.nextInt((high-low)+1) + low));
        T swap;
        System.out.println("Pivot List: " + arr.toString());
        if(arr.get(0).compareTo(arr.get(2)) > 0) {
            swap = arr.get(0);
            arr.set(0, arr.get(2));
            arr.set(2, swap);
        }
        if(arr.get(1).compareTo(arr.get(2)) > 0) {
            swap = arr.get(1);
            arr.set(1, arr.get(2));
            arr.set(2, swap);
        }
        if(arr.get(0).compareTo(arr.get(1)) > 0) {
            swap = arr.get(0);
            arr.set(0, arr.get(1));
            arr.set(1, swap);
        }
        System.out.println("Pivot List: " + arr.toString());
        return list.indexOf(arr.get(1));
    }
 
Thema: 

Quicksort

Passende Stellenanzeigen aus deiner Region:
Anzeige

Neue Themen

Anzeige

Anzeige
Oben