Quicksort är en dela-och-erövra-sortering som väljer en pivot, partitionerar element i de mindre och större än den, sedan rekursivt sorterar varje sida. Genomsnittligt O(n log n), värsta fall O(n²).
Partitionering placerar pivot i dess slutgiltiga sorterade position; allt till vänster är mindre, allt till höger är större. Rekursera på båda sidorna.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2] # pick a pivot
left = [x for x in arr if x < pivot] # smaller
mid = [x for x in arr if x == pivot] # equal
right = [x for x in arr if x > pivot] # larger
return quicksort(left) + mid + quicksort(right)
quicksort([5, 2, 8, 1, 3]) # -> [1, 2, 3, 5, 8]
(In-place-partitionering används i praktiken för att spara minne.)
| Fall | Tid | Orsak |
|---|---|---|
| Best/Average | O(n log n) | balanserade partitioner |
| Worst | O(n²) | redan sorterad med dålig pivot |
In-place quicksort använder O(log n) stackutrymme.
Vanligtvis den snabbaste i praktiken på grund av cache-vänlighet och låg overhead, och det är in-place. Det värsta fallet O(n²) undviks med en randomiserad eller median-av-tre pivot. Det är inte stabilt.
Quicksort är standard i många standardbibliotek på grund av dess utmärkta genomsnittliga hastighet och låg minnesanvändning.
Att förstå varför pivotval orsakar det värsta fallet O(n²) lär en nyckellektion: genomsnittligt och värsta fall kan skilja sig markant åt.
Det är ett favoritintervjuämne just på grund av denna nyans.