Informatik

Wie funktioniert Quicksort?

Quicksort ist ein Divide & Conquer Sortierverfahren: Man wählt ein Pivot $p$, partitioniert in Elemente $e \leq p$ und Elemente $e > p$, sortiert die Teilbereiche rekursiv und setzt zusammen.

Algorithmus

• Pivot $p$ wählen
• Partitionieren: $\text{links}\,(\leq)$, $\text{rechts}\,(>)$
• Rekursiv sortieren: $\text{quicksort}(\text{links}) + [p] + \text{quicksort}(\text{rechts})$

Pseudocode

quicksort(array):
    wenn Länge(array) <= 1:
        return array

    pivot = array[0]
    links = []
    rechts = []
    für element in array[1:]:
        wenn element <= pivot:
            links.append(element)
        sonst:
            rechts.append(element)
    
    return quicksort(links) + [pivot] + quicksort(rechts)

Beispiel

Input: $[3,7,2,5,1]$

$p = 3$; Partitionieren:

Rekursiv sortieren:

Zusammenfügen: