Quicksort

[Kirby.exe]

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



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:

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

 

[kneitzel]

Du kannst dir den Algorithmus z.B. bei Wikipedia ansehen: https://de.m.wikipedia.org/wiki/Quicksort

Da wird dann z.B. einfach das Rechte Element genommen um dann von links nach zu tauschenden Elementen zu schauen....

 

[Kirby.exe]

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

 

[mihe7]

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)

... wenn die Elemente sortiert sind ("Der Median der Messwerte einer Urliste ist derjenige Messwert, der genau „in der Mitte“ steht, wenn man die Messwerte der Größe nach sortiert." - https://de.wikipedia.org/wiki/Median)

 

[Kirby.exe]

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

 

[Kirby.exe]

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

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