Quicksort

Einfache Sprache

Simple Quicksort

Idee simple Quicksort

Gegeben ist ein Feld $A$ mit $n$ ganzen Zahlen. Simple Quicksort funktioniert folgendermaßen: Zuerst wähle ein Pivotelement $x$ aus $A$. Dann ordne $A$ so um, dass zwei Teilfelder entstehen, wobei die Elemente im linken Teil $\leq x$ und im rechten Reil $\geq x$ sind. Dann sortiere die beiden Teilfelder rekursiv.

Algorithmus

 1def quicksort(A, l, r):
 2    if l < r:
 3        x = A[l]
 4        i = l
 5        for j in range(l + 1, r + 1):
 6            if A[j] <= x:
 7                i += 1
 8                A[i], A[j] = A[j], A[i]
 9        A[l], A[i] = A[i], A[l]
10        quicksort(A, l, i - 1)
11        quicksort(A, i + 1, r)

Laufzeit

Wenn alle Eingabenpermutationen gleich wahrscheinlich sind ist die Durchschnittslaufzeit $\mathcal O(n\log n)$. Im Worst case aber $\mathcal O(n^2)$.

Der Algorithmus Simple Quicksort benötigt ein zusätzliches Feld $B$ der gleichen Größe wie $A$. Der Schritt Reorder funktioniert so, dass zunächst alle Zahlen $\leq x$, dann $x$ und danach die Zahlen $\geq x$ nach $B$ kopiert. Die in-place Variate von Quicksort braucht das nicht.

In-place Quicksort

Idee in-place Quicksort

Verwende zwei Indizes $i$ und $j$. Initialisiere sie so, dass $i=l+1$ und $j=r$. Solange $l

• Lasse $i$ von links nach rechts über $A$ laufen bis $A[i]>x$ oder $i>j$ ist.
• Lasse $j$ von rechts nach links über $A$ laufen bis $A[j]j$ ist.
• Vertausche $A[i]$ und $A[j]$ falls $i

Zum Schluss füge das Pivotelement an Position $i-1=j$ ein. Also vertausche $A[l]$ mit $A[i-1]$ wenn das Pivotelement $A[l]$ ist.

Algorithmus

 1def in_place_quicksort(A, l, r):
 2    if l < r:
 3        x = A[l]
 4        i = l + 1
 5        j = r
 6        while i <= j:
 7            while i <= j and A[i] <= x:
 8                i += 1
 9            while i <= j and A[j] >= x:
10                j -= 1
11            if i < j:
12                temp = A[i]
13                A[i] = A[j]
14                A[j] = temp
15        i -= 1
16        A[l] = A[i]
17        A[i] = x
18        in_place_quicksort(A, l, i - 1)
19        in_place_quicksort(A, i + 1, r)

Randomisiertes Quicksort

Idee randomisiertes Quicksort

Die Laufzeit von Quicksort hängt von der Differenz der Teilfeldgrößen ab. Also wenn z.B. links große 1 hat und rechts den Rest. Die Wahrscheinlichkeitsverteilung der Eingabe ist somit entscheidend. Das können wir umgehen indem wir ein zufälliges Pivotelement auswählen. Der resultierende Algorithmus ist daher nur durch die Wahl von $x$ von den vorherigen zu unterscheiden.

Algorithmus

 1import random
 2
 3def randomized_quicksort(A, l, r):
 4    if l < r:
 5        # Random pivot selection
 6        k = random.randint(l, r)
 7        x = A[k]
 8        # Swap pivot with first element
 9        A[k], A[l] = A[l], A[k]
10        
11        # Partitioning (Lomuto scheme)
12        i = l
13        for j in range(l + 1, r + 1):
14            if A[j] <= x:
15                i += 1
16                A[i], A[j] = A[j], A[i]
17        # Put pivot in correct position
18        A[l], A[i] = A[i], A[l]
19        
20        # Recursive calls
21        randomized_quicksort(A, l, i - 1)
22        randomized_quicksort(A, i + 1, r)

Laufzeit

Die Durchschnittslaufzeit von Randomized Quicksort ist $\mathcal O(n\log n)$. Der Erwartungswert von Vergleiche für das Sortieren eines Feldes der Länge $n$ ist $\approx 1.3863n\log n$.

Median-basiertes Quicksort

Wenn wir im Quicksort Algorithmus als Pivotelement jeweils den Median der Zahlen $A[l], \ldots , A[r]$ wählen, so erhalten wir als Gesamtlaufzeit $\mathcal O(n \log n)$.