Quicksort

08 Oct 2017 • Rekursion und Backtracking • Beiträge

Mit Quicksort haben wir im Unterricht einen weiteren Sortieralgorithmus behandelt, der nochmals effektiver ist, als die bisherigen Sortierverfahren.

Prinzip:

Beispiel Quicksort Quelle: http://www.stoimen.com/blog/2012/03/13/computer-algorithms-quicksort/

Wie wir in der obigen Abbildung erkennen können, wird in Quicksort zuerst ein Pivot-Element bestimmt. Vom Prinzip her kann dieses beliebig sein, ich werde aber später noch auf die beste Wahl eingehen. Nachdem wir nun das Element bestimmt haben, sortieren wir die Werte in der Menge so, dass auf der einen Seite des Pivot-Elementes alle Werte stehen, die kleiner als das Element sind, und auf der anderen Seite alle Werte, die größer sind. In beiden Mengen, also links und rechts vom Pivot-Element führen wir nun wieder dieses Verfahren durch, bis immer nur noch ein Wert in der betrachteten Menge übrig ist.

Pseudocode

function quicksort(low, high)

wenn rechts-links<1 
    dann gib zurück 

bestimme pivot 
links = low 
rechts = high 

solange rechts > links mache
    solange wert von links < pivot 
        gehe weiter nach rechts 
    solange werte von rechts > pivot
        gehe weiter nach links
    tausche rechts und links

quicksort(low, rechts-1)
quicksort(rechts+1, high)

Die Rekursionsbasis besteht dabei aus der Verzweigung, die Überprüft, ob es nur noch einen Wert gibt. In dem Rekursionsschritt wird dann das Pivot-Element festgelegt. Dannach folgt eine Schleife, die solange durchläuft, bis rechts <= links ist. Das bedeutet, dass sie abbricht, wenn alle Werte innerhalb der Menge überprüft wurden. Die beiden weiteren Schleifen gehen einmal von links nach rechts, und einmal von rechts nach links im Array. Beide stoppen,wenn sie einen Wert finden, der eigentlich auf die andere Seite von dem Pivot Element gehört. Die jeweils gefundenen Elemente werden dann getauscht. Für Beide Bereiche wird dann die Methode rekursiv aufgerufen. Einmal für links vom Pivot und einmal rechts vom Pivot. Wir habe nun das Pivot Element an die richtige Stelle einsortiert.

Implementierung

public void quickSort(int low, int high){
    //Basis: Sollte nur noch ein Element in der Menge sein
    if(high-low < 1) return;

    int pivot = array[(high+low)/2]; // Pivot Mitte
    int links = low;
    int rechts = high;

    //Die Pointer duerfen sich nicht treffen.
    while (rechts > links){
        //Auf der linken Seite falsche Stelle suchen
        while (array[links]< pivot){
            links++;
        }
        //Auf der rechten Seite falsche Stelle suchen
        while (array[rechts] > pivot){
            rechts--;
        }
        tausche(links, rechts);
    }
    
    quickSort(low, rechts-1);
    quickSort(rechts+1, high);
}

Struktogramm

Struktogramm

Laufzeit

Wie oben schone einmal angesprochen, ist die Laufzeit des Algorithmuses sehr von der Wahl des Pivot-Elementes abhängig. Hierbei lässt sich diese Abhängigkeit gut mit dem Worst Case und dem Best Case beschreiben.

Der Worst Case wäre, wenn das Pivot-Element ein Randelement ist. Also an Stelle 0 oder an Stelle array.lenght-1 relativ zur Wertemenge gesehen, da wir dann die Rekursiven Aufrufe nicht gleichmäßig verteilen würden und einer der beiden Aufrufe immer die gesamte Menge überprüfen würde.

Der Best Case wäre, wenn das Pivot-Element der Median wäre. Würde das Sortieren für diesen Schritt wegfallen, da alle Werte schon auf der richtigen Seite stehen. Da zur Findung des Medians ein sortiertes Array von nöten wäre, wählen wir wenigstens immer den mittleren Wert um eine gleiche Verteilung zu erzielen. Wichtig ist nur, dass wir kein Randwert erwischen, also der worst case eintreten würde , weil dann die Laufzeit von Quicksort die gleiche wie die von Bubblesort wäre.

Im Best- und Average Case wäre die Laufzeit $$ O(n*log(n)) $$ Im Worst Case wäre die Laufzeit n².

Related Posts