Quick Sort und Pivot-Auswahl
Implementieren Sie Quick Sort mit den Partitionierungsverfahren von Lomuto und Hoare, besprechen Sie den Worst Case O(n²) und wie eine zufällige Pivot-Auswahl ihn abmildert.
Quick Sort und Pivot-Auswahl ist eine kostenlose DSA Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des DSA Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Quick Sort: In-Place-Teile-und-herrsche
Quick Sort ist in der Praxis der am weitesten verbreitete Sortieralgorithmus. Im Gegensatz zu Merge Sort sortiert er in-place, ohne zusätzliche Arrays zu reservieren. Die Grundidee: Wählen Sie ein Pivot-Element, partitionieren Sie das Array so, dass alle Elemente, die kleiner als das Pivot sind, davor und alle größeren Elemente danach stehen, und sortieren Sie anschließend jede Partition rekursiv. Der Partitionierungsschritt benötigt O(n) Zeit, und bei einem guten Pivot beträgt die Rekursionstiefe O(log n).
def quick_sort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
pivot_idx = partition(arr, lo, hi)
quick_sort(arr, lo, pivot_idx - 1) # sort left
quick_sort(arr, pivot_idx + 1, hi) # sort right
def partition(arr, lo, hi):
pivot = arr[hi] # Lomuto: choose last element as pivot
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Lomuto-Partitionsschema
Die Lomuto-Partitionierung verwendet das letzte Element als Pivot. Ein langsamer Zeiger i verfolgt die Grenze des Bereichs „kleiner als das Pivot“, während ein schneller Zeiger j vorwärts scannt. Wenn arr[j] <= pivot gilt, erhöhen Sie i und vertauschen arr[i] mit arr[j], wodurch der Bereich der kleineren Elemente erweitert wird. Platzieren Sie das Pivot nach dem Scan bei i+1, indem Sie es mit arr[hi] vertauschen. Einfach zu implementieren, führt aber zu 3× mehr Vertauschungen als das Hoare-Schema.
def lomuto_partition_traced(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
print(f'Pivot: {pivot}, array: {arr[lo:hi+1]}')
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
print(f'After partition: {arr[lo:hi+1]}')
return i + 1
arr = [3, 1, 4, 1, 5, 9, 2, 6]
lomuto_partition_traced(arr, 0, len(arr)-1)Hoare-Partitionsschema
Die Hoare-Partitionierung verwendet zwei Zeiger, die an den beiden Enden beginnen und sich nach innen bewegen, bis sie sich kreuzen. Sie wählt das Pivot (normalerweise das erste Element) und verschiebt kleinere Elemente nach links und größere nach rechts. Das Hoare-Schema benötigt 3× weniger Vertauschungen als Lomuto und funktioniert besser mit gleichen Elementen, aber das Pivot befindet sich nach der Partitionierung nicht an seiner endgültigen Position – daher sind leicht andere rekursive Aufrufe erforderlich.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1
j -= 1
while arr[j] > pivot: j -= 1
if i >= j: return j
arr[i], arr[j] = arr[j], arr[i]
def quick_sort_hoare(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quick_sort_hoare(arr, lo, p) # note: p not p-1
quick_sort_hoare(arr, p+1, hi)
arr = [3, 6, 8, 10, 1, 2, 1]
quick_sort_hoare(arr)
print(arr) # [1, 1, 2, 3, 6, 8, 10]Worst Case O(n²): Bereits sortierte Eingabe
Der Worst Case von Quick Sort tritt auf, wenn das Pivot durchgehend das kleinste oder größte Element der Partition ist. Bei Lomutos Pivot-Auswahl des letzten Elements in einem bereits sortierten Array platziert die Partitionierung immer 0 Elemente links und n-1 rechts: Der Rekursionsbaum degeneriert zu einer Kette der Tiefe n, wodurch O(n²) Vergleiche entstehen. Deshalb ist die Pivot-Auswahl entscheidend und Produktionsimplementierungen das Pivot zufällig wählen.
import sys
sys.setrecursionlimit(5000)
def quick_sort_naive(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
comparisons = [0]
def _qs(lo, hi):
if lo >= hi: return
pivot = arr[hi] # last element pivot
i = lo - 1
for j in range(lo, hi):
comparisons[0] += 1
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
_qs(lo, p-1); _qs(p+1, hi)
_qs(lo, hi)
return comparisons[0]
import math
n = 100
sorted_arr = list(range(n))
ops = quick_sort_naive(sorted_arr)
print(f'n={n}, ops={ops}, n^2={n**2}') # ops close to n*(n-1)/2Randomisiertes Pivot: Erwartete Laufzeit O(n log n)
Indem das Pivot gleichverteilt zufällig gewählt wird (ein zufälliges Element wird vor der Partitionierung mit arr[hi] vertauscht), sinkt die Wahrscheinlichkeit, durchgehend schlechte Pivots auszuwählen, exponentiell. Die erwartete Anzahl der Vergleiche beträgt 2n ln(n) ≈ 1.39 n log₂(n), was mit überwältigender Wahrscheinlichkeit eine erwartete Laufzeit von O(n log n) ergibt. Deshalb wird randomisierter Quick Sort in der Praxis verwendet: Er vermeidet pathologische Worst Cases, die ein Angreifer für Strategien mit festem Pivot konstruieren könnte.
import random
def quick_sort_random(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
# Randomise pivot
rand_i = random.randint(lo, hi)
arr[rand_i], arr[hi] = arr[hi], arr[rand_i]
# Lomuto partition with last element as pivot
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
p = i + 1
quick_sort_random(arr, lo, p - 1)
quick_sort_random(arr, p + 1, hi)
arr = list(range(100, 0, -1)) # worst case for naive
quick_sort_random(arr)
print(arr[:10]) # [1,2,3,4,5,6,7,8,9,10]Median aus drei Elementen als Pivot
Eine weitere Pivot-Strategie: Wählen Sie den Median des ersten, mittleren und letzten Elements. Dadurch wird ein Verhalten im Worst Case bei sortierten oder umgekehrt sortierten Eingaben vermieden (den häufigsten adversarialen Eingaben), ohne den Aufwand der Erzeugung von Zufallszahlen. Viele Produktionsimplementierungen verwenden bei großen Arrays den Median aus drei Elementen oder einen Ninther (den Median aus drei Medianen) und wechseln bei kleinen Teilarrays unterhalb eines Schwellenwerts von ~10 Elementen zu Insertion Sort.
def median_of_three(arr, lo, hi):
mid = (lo + hi) // 2
# Sort lo, mid, hi values in place
if arr[lo] > arr[mid]: arr[lo], arr[mid] = arr[mid], arr[lo]
if arr[lo] > arr[hi]: arr[lo], arr[hi] = arr[hi], arr[lo]
if arr[mid] > arr[hi]: arr[mid], arr[hi] = arr[hi], arr[mid]
# Median is now at arr[mid]; swap to arr[hi-1] as pivot
arr[mid], arr[hi] = arr[hi], arr[mid]
return arr[hi] # pivot value
arr = [3, 9, 1]
print(median_of_three(arr, 0, 2), arr) # 3, [1,3,9] (sorted)Dutch National Flag: Drei-Wege-Partitionierung
Bei der standardmäßigen Partitionierung werden Elemente, die kleiner als das Pivot sind, links und größere rechts platziert, während Elemente, die dem Pivot entsprechen, verteilt bleiben. Die Drei-Wege-Partitionierung (Dutch National Flag) erstellt drei Bereiche: <pivot, ==pivot, >pivot. Das ist für Arrays mit vielen Duplikaten entscheidend – bei ihnen verschlechtert sich der standardmäßige Quick Sort auf O(n²), während ein Drei-Wege-Quick-Sort bei Eingaben mit nur einem Wert O(n) erreicht.
def three_way_partition(arr, lo, hi):
pivot = arr[lo]
lt = lo # arr[lo..lt-1] < pivot
gt = hi # arr[gt+1..hi] > pivot
i = lo # current
while i <= gt:
if arr[i] < pivot:
arr[lt], arr[i] = arr[i], arr[lt]
lt += 1; i += 1
elif arr[i] > pivot:
arr[i], arr[gt] = arr[gt], arr[i]
gt -= 1 # don't advance i
else:
i += 1
return lt, gt # pivot occupies arr[lt..gt]
arr = [3, 1, 4, 1, 5, 9, 2, 6, 3, 3]
lt, gt = three_way_partition(arr, 0, len(arr)-1)
print(arr, '| pivot region:', lt, 'to', gt)Quickselect: k-kleinstes Element in O(n)
Quickselect verwendet den Partitionierungsschritt von Quick Sort, um das k-kleinste Element mit einer durchschnittlichen Laufzeit von O(n) zu finden, ohne das Array vollständig zu sortieren. Nach der Partitionierung befindet sich das Pivot an seiner endgültigen Position p. Wenn p == k gilt, geben Sie arr[p] zurück. Wenn k < p gilt, führen Sie die Rekursion auf der linken Partition fort; wenn k > p gilt, auf der rechten. Im Durchschnitt halbiert jede Rekursion das Problem: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).
import random
def quickselect(nums, k):
'''Find kth smallest (0-indexed) in O(n) average.'''
def _select(lo, hi):
if lo == hi: return nums[lo]
rand_i = random.randint(lo, hi)
nums[rand_i], nums[hi] = nums[hi], nums[rand_i]
pivot = nums[hi]
i = lo - 1
for j in range(lo, hi):
if nums[j] <= pivot:
i += 1; nums[i], nums[j] = nums[j], nums[i]
p = i + 1
nums[p], nums[hi] = nums[hi], nums[p]
if p == k: return nums[p]
elif k < p: return _select(lo, p - 1)
else: return _select(p + 1, hi)
return _select(0, len(nums) - 1)
print(quickselect([3,2,1,5,6,4], 1)) # 2 (2nd smallest)Speicherkomplexität von Quick Sort
Quick Sort wird als „in-place“ bezeichnet, benötigt für die Rekursion aber durchschnittlich O(log n) Stack-Speicher (einen Stack-Frame pro Ebene des Rekursionsbaums). Im Worst Case beträgt die Stack-Tiefe O(n). Um im Worst Case eine Stack-Tiefe von O(log n) zu garantieren, führen Sie die Rekursion immer zuerst für die kleinere Partition aus und verwenden Sie für die größere Partition eine Tail-Call-Optimierung. Pythons Rekursionslimit macht sehr tiefe Quick-Sort-Rekursionen riskant – das ist in Vorstellungsgesprächen erwähnenswert.
def quick_sort_optimised(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
while lo < hi:
p = lomuto_partition_qs(arr, lo, hi)
# Recurse on smaller partition; iterate on larger
if p - lo < hi - p:
quick_sort_optimised(arr, lo, p - 1)
lo = p + 1 # tail-call elimination
else:
quick_sort_optimised(arr, p + 1, hi)
hi = p - 1
def lomuto_partition_qs(arr, lo, hi):
pivot = arr[hi]; i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot: i += 1; arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1]
return i + 1Sortieralgorithmen im Vergleich
Fassen Sie Ihr Wissen zusammen:
- Quick Sort: erwartetes O(n log n), O(n²) im Worst Case, O(log n) Speicher, instabil, in der Praxis am schnellsten bei zufälligen Daten
- Merge Sort: garantiert O(n log n), O(n) Speicher, stabil, am besten für verkettete Listen und externes Sortieren
- Heap Sort: garantiert O(n log n), O(1) Speicher, instabil, in der Praxis aufgrund von Cache-Fehlzugriffen langsamer
- Insertion Sort: O(n) im Best Case, ideal für kleine n oder nahezu sortierte Daten
# Python's sorted() uses Timsort:
# - Hybrid: merge sort for large runs, insertion sort for small (< 64 elements)
# - Stable, O(n log n) worst case
# - O(n) best case for sorted/reverse-sorted/nearly-sorted
# - O(n) extra space
import random
arr = random.sample(range(10000), 1000)
sorted_arr = sorted(arr) # Timsort
print(sorted_arr[:5], '...') # first 5 elementsIntrosort: Alle drei kombinieren
Introsort (verwendet in der C++-STL std::sort) kombiniert Quick Sort, Heap Sort und Insertion Sort: Starten Sie mit randomisiertem Quick Sort; wenn die Rekursionstiefe 2 log n überschreitet (was auf eine schlechte Pivot-Folge hindeutet), wechseln Sie zu Heap Sort, um O(n log n) zu garantieren; verwenden Sie Insertion Sort für Teilarrays mit weniger als 16 Elementen. Dadurch ergibt sich ein Worst Case von O(n log n) bei der Geschwindigkeit von Quick Sort im Durchschnitt und der Effizienz von Insertion Sort für kleine Teilarrays.
# Introsort hybrid (simplified)
def introsort(arr, depth_limit=None):
if depth_limit is None:
import math
depth_limit = 2 * int(math.log2(len(arr) + 1)) if arr else 0
if len(arr) <= 16:
# insertion sort for small arrays
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1
arr[j+1] = key
return arr
if depth_limit == 0:
arr.sort() # fall back to heapsort equivalent
return arr
# Otherwise quick sort
pivot = arr[-1]
small = [x for x in arr[:-1] if x <= pivot]
large = [x for x in arr[:-1] if x > pivot]
return introsort(small, depth_limit-1) + [pivot] + introsort(large, depth_limit-1)
print(introsort([5,3,8,1,9,2,7]))Wissenscheck
Überprüfen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep in dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Quick Sort partitioniert in-place um ein Pivot und ruft sich für jede Seite rekursiv auf, wodurch eine erwartete Laufzeit von O(n log n) bei O(log n) Stack-Speicher erreicht wird – bei zufälligen Daten in der Praxis schneller als Merge Sort, der Worst Case O(n²) bei sortierter Eingabe mit einem festen Pivot auftritt und durch eine randomisierte Pivot-Auswahl oder den Median aus drei Elementen vermieden wird, und die Drei-Wege-Partitionierung Duplikate effizient verarbeitet und Quickselect die Partitionierungsidee erweitert, um das k-kleinste Element mit einer durchschnittlichen Laufzeit von O(n) ohne vollständiges Sortieren zu finden. Als Nächstes untersuchen wir nicht vergleichsbasierte Sortierverfahren und Pythons integrierte Sortierung.
Häufig gestellte Fragen
Ist die Lektion „Quick Sort und Pivot-Auswahl“ kostenlos?
Ja — der vollständige Text von „Quick Sort und Pivot-Auswahl“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des DSA Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der DSA Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Quick Sort und Pivot-Auswahl“?
Implementieren Sie Quick Sort mit den Partitionierungsverfahren von Lomuto und Hoare, besprechen Sie den Worst Case O(n²) und wie eine zufällige Pivot-Auswahl ihn abmildert. Du übst DSA Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um DSA Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. DSA Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 3 von 4.
Wie lange dauert die Lektion „Quick Sort und Pivot-Auswahl“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser DSA Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede DSA Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Bubble Sort und Insertion Sort
- Merge Sort: Teilen, sortieren, zusammenführen
- Quick Sort und Pivot-Auswahl
- Nicht vergleichende Sortierverfahren und Pythons sort()