Quicksort-Algorithmus

Text von KI erstellt

Der Quicksort-Algorithmus ist ein effizientes, rekursives Sortierverfahren, das nach dem Teile-und-Herrsche-Prinzip (Divide and Conquer) funktioniert. Er wurde 1959 von Tony Hoare entwickelt und ist einer der schnellsten Sortieralgorithmen für große Datensätze.

Funktionsweise

Quicksort funktioniert, indem es eine Liste in kleinere Teillisten aufteilt, diese rekursiv sortiert und dann wieder zusammenführt.

Auswahl des Pivots

Ein Element der Liste wird als Pivot ausgewählt. Üblicherweise wird das letzte, erste oder ein zufälliges Element der Liste gewählt.

Partitionierung

Die Liste wird so umsortiert, dass alle Elemente, die kleiner als das Pivot sind, links davon stehen, und alle Elemente, die größer sind, rechts davon.

Rekursive Sortierung

Die beiden Teillisten (links und rechts des Pivots) werden rekursiv mit Quicksort sortiert.

Implementierung in Python

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[-1]  # Wähle das letzte Element als Pivot
        left = [x for x in arr[:-1] if x <= pivot]
        right = [x for x in arr[:-1] if x > pivot]
        return quicksort(left) + [pivot] + quicksort(right)

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

Beispielablauf

Schritt 1: Auswahl des Pivots

Angenommen, die Liste ist [3, 6, 8, 10, 1, 2, 1]. Das letzte Element 1 wird als Pivot gewählt.

Schritt 2: Partitionierung

Linke Teilliste: [1, 1] (alle Elemente ≤ Pivot)
Rechte Teilliste: [3, 6, 8, 10, 2] (alle Elemente > Pivot)

Schritt 3: Rekursive Sortierung

Die Teillisten werden rekursiv sortiert, bis die gesamte Liste sortiert ist.

Zeitkomplexität

Fall	Komplexität
Best Case	O(n log n)
Average Case	O(n log n)
Worst Case	O(n²)