Leitfaden zum Python-Quicksort-Algorithmus

Entdecken Sie den Quicksort-Algorithmus in Python. Lernen Sie Pivot-Auswahl, Partitionierung und Rekursion in diesem interaktiven Codierungsbeispiel.

Versuchen Sie es im Editor

Übersicht

Quicksort ist ein extrem schneller und weit verbreiteter Sortieralgorithmus. Wie die Zusammenführungssortierung wird ein Divide-and-Conquer-Ansatz verwendet. Quicksort sortiert die Elemente jedoch „an Ort und Stelle“ und macht es so speichereffizient.

Der Algorithmus funktioniert, indem er ein „Pivot“-Element aus der Liste auswählt. Anschließend werden die anderen Elemente in zwei Unterarrays unterteilt: diejenigen, die kleiner als der Pivot sind, und diejenigen, die größer als der Pivot sind. Dieser Prozess wird rekursiv auf die Unterarrays angewendet.

Obwohl Quicksort im ungünstigsten Fall eine Komplexität von O(n²) aufweist, beträgt die durchschnittliche Laufzeit O(n log n) und in der Praxis übertrifft es in der Regel die Zusammenführungssortierung aufgrund der geringeren Cache-Fehler und des Nullaufwands für die Erstellung temporärer Arrays.

Code- und Ausführungsausgabe

Ein prägnantes rekursives Schnellsortierungsskript, das Listenverständnisse für eine hohe Lesbarkeit nutzt.

quicksort.py

Versuchen Sie es im Editor

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[len(arr) // 2]
        left = [x for x in arr if x < pivot]
        middle = [x for x in arr if x == pivot]
        right = [x for x in arr if x > pivot]
        return quicksort(left) + middle + quicksort(right)

# Test list
data = [12, 4, 5, 6, 7, 3, 1, 15]
print("Original List:", data)
sorted_data = quicksort(data)
print("Sorted List:  ", sorted_data)

Terminal-Ausgabe

Original List: [12, 4, 5, 6, 7, 3, 1, 15]
Sorted List:   [1, 3, 4, 5, 6, 7, 12, 15]

Schrittweise Umsetzung

Systemsortierroutinen, bei denen der Speicherbedarf auf ein Minimum beschränkt werden muss
Universelle Sortierung in Standard-Sprachbibliotheks-Frameworks
Akademische Lehre der Partitionsmechanik und des rekursiven Teilens und Eroberns

Häufig gestellte Fragen

Wie können wir die Worst-Case-Komplexität von O(n²) in Quicksort vermeiden?

Der schlimmste Fall tritt auf, wenn der ausgewählte Pivot wiederholt das kleinste oder größte Element ist. Um dies zu mildern, verwenden Entwickler Strategien wie die Auswahl eines zufälligen Pivots oder des „Medians von drei“ Werten.

Ist Quicksort stabil?

Nein, Standard-Quicksort ist instabil. Bei der Partitionierung werden Elemente über große Bereiche hinweg vertauscht, wodurch sich die relative Reihenfolge doppelter Elemente ändern kann.