Quicksort

9.1 Definition von Quicksort

Quicksort ist ein effizienter Sortieralgorithmus, der das "Teile und herrsche"-Prinzip verwendet. Er arbeitet, indem er ein Pivot-Element wählt, das Array in zwei Teilarrays aufteilt – Elemente, die kleiner als das Pivot sind, und Elemente, die größer sind – und dann denselben Prozess rekursiv auf jedes Teilarray anwendet.

Der Quicksort-Algorithmus entstand als Versuch, das Problem zu lösen: "Wie kann man kleinere Elemente möglichst schnell nach links verschieben und größere nach rechts?" Angenommen, das kleinste Element befindet sich ganz rechts, kann man es irgendwie schnell verschieben, wenn nicht an seine endgültige Position, dann zumindest nahe daran? Das würde die Anzahl unnötiger Vergleiche erheblich reduzieren.

Arbeitsprinzip:

1. Auswahl eines Pivots:

Man wählt ein Element aus dem Array als Pivot. Das kann das erste, letzte, mittlere oder ein zufälliges Element sein. Manchmal ist es der Durchschnitt dreier zufälliger Elemente.

2. Aufteilung (Partitioning):

Man verschiebt alle Elemente, die kleiner als das Pivot sind, in den linken Teil des Arrays und alle Elemente, die größer sind, in den rechten Teil. Am Ende befindet sich das Pivot-Element an seiner endgültigen Position im sortierten Array.

3. Rekursive Anwendung:

Der Prozess wird rekursiv auf die linken und rechten Teilarrays angewendet, das Pivot-Element wird dabei nicht wiederholt.

Schritt-für-Schritt-Prozess

1. Wir wählen ein Pivot-Element.
2. Wir verschieben die kleineren Elemente nach links und die größeren nach rechts.
3. Wir wenden den Prozess rekursiv auf die Teilarrays an.

Zeit- und Platzkomplexität von Quicksort

Zeitkomplexität:

• Im schlimmsten Fall: O(n^2) – tritt auf, wenn jedes Mal das schlechteste Pivot-Element gewählt wird (z.B. wenn das Array bereits sortiert ist).
• Im Durchschnittsfall: O(n log n) – für zufällig verteilte Daten.
• Im besten Fall: O(n log n) – wenn das Array jedes Mal in gleich große Teile geteilt wird.

Platzkomplexität:

O(log n) – ist erforderlich, um den Aufrufstack der Rekursion zu speichern, wenn Tail Rekursion benutzt wird und die Pivot-Elemente günstig gewählt werden.

9.2 Implementierung des Quicksort-Algorithmus

Python-Implementierung:

def quick_sort(arr):
    if len(arr) <= 1:
        return arr  # Basisfall: Array mit 0 oder 1 Element ist bereits sortiert
    
    pivot = arr[len(arr) // 2]  # Wir wählen ein Pivot-Element
    left = [x for x in arr if x < pivot]  # Elemente, die kleiner als das Pivot sind
    middle = [x for x in arr if x == pivot]  # Elemente, die gleich dem Pivot sind
    right = [x for x in arr if x > pivot]  # Elemente, die größer als das Pivot sind
    
    return quick_sort(left) + middle + quick_sort(right)

# Beispielverwendung:
arr = [3, 6, 8, 10, 1, 2, 1]
sorted_arr = quick_sort(arr)
print("Sortiertes Array:", sorted_arr)
# Ausgabe: Sortiertes Array: [1, 1, 2, 3, 6, 8, 10]

Beispiel für die Arbeitsweise des Algorithmus

Nehmen wir ein Beispielarray: [3, 6, 8, 10, 1, 2, 1]

Erster Durchlauf:

• Pivot-Element: 8
• Linke Elemente: [3, 6, 1, 2, 1]
• Mittlere Elemente: [8]
• Rechte Elemente: [10]

Rekursive Sortierung des linken Teils [3, 6, 1, 2, 1]:

• Pivot-Element: 1
• Linke Elemente: []
• Mittlere Elemente: [1, 1]
• Rechte Elemente: [3, 6, 2]

Rekursive Sortierung des rechten Teils [3, 6, 2]:

• Pivot-Element: 6
• Linke Elemente: [3, 2]
• Mittlere Elemente: [6]
• Rechte Elemente: []

Rekursive Sortierung des linken Teils [3, 2]:

• Pivot-Element: 2
• Linke Elemente: []
• Mittlere Elemente: [2]
• Rechte Elemente: [3]

Ergebnis der Zusammenführung: [1, 1, 2, 3, 6] für den linken Teil, [10] für den rechten Teil, und [8] für den mittleren.

Endgültiges sortiertes Array: [1, 1, 2, 3, 6, 8, 10]