Quick sort og valg af pivot
Opbyg quick sort med Lomuto- og Hoare-partitionering, og gennemgå worst-case O(n²) samt hvordan randomiseret pivotvalg afhjælper det.
Quick sort og valg af pivot er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Quicksort: del og hersk på stedet
Quicksort er den mest udbredte sorteringsalgoritme i praksis. I modsætning til mergesort sorterer den in-place uden at allokere ekstra arrays. Grundideen er at vælge et pivot-element, opdele arrayet, så alle elementer, der er mindre end pivotten, kommer før den, og alle større elementer kommer efter den, og derefter sortere hver del rekursivt. Opdelingstrinnet tager O(n) tid, og med en god pivot er rekursionsdybden 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]Lomutos opdelingsmetode
Lomuto-partitionering bruger det sidste element som pivot. En langsom pointer i holder styr på grænsen for området med ’mindre end pivotten’; en hurtig pointer j scanner fremad. Når arr[j] <= pivot, øges i, og arr[i] ombyttes med arr[j], så området med små elementer udvides. Efter scanningen placeres pivotten på i+1 ved at ombytte den med arr[hi]. Den er let at implementere, men udfører 3× flere ombytninger end Hoares metode.
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)Hoares opdelingsmetode
Hoare-partitionering bruger to pointere, der starter i hver sin ende og bevæger sig ind mod hinanden, indtil de krydser hinanden. Den vælger pivotten (sædvanligvis det første element) og flytter elementer, der er mindre end pivotten, til venstre og større elementer til højre. Hoares metode udfører 3× færre ombytninger end Lomutos og fungerer bedre med ens elementer, men pivotten ender ikke på sin endelige placering efter partitioneringen — derfor kræves der lidt anderledes rekursive kald.
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]Værste tilfælde O(n²): allerede sorterede inddata
Quicksorts værste tilfælde opstår, når pivotten konsekvent er det mindste eller største element i partitionen. Med Lomutos pivot fra det sidste element på et allerede sorteret array placerer partitioneringen altid 0 elementer til venstre og n-1 til højre: Rekursionstræet degenererer til en kæde med dybden n, hvilket giver O(n²) sammenligninger. Derfor er valg af pivot afgørende, og derfor randomiserer implementeringer i produktion pivotten.
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)/2Tilfældig pivot: forventet O(n log n)
Ved at vælge pivotten ensartet tilfældigt (ombyt et tilfældigt element med arr[hi] før partitioneringen) falder sandsynligheden for konsekvent at vælge dårlige pivoter eksponentielt. Det forventede antal sammenligninger er 2n ln(n) ≈ 1.39 n log₂(n), hvilket giver forventet tidsforbrug på O(n log n) med overvældende sandsynlighed. Derfor bruges randomiseret quicksort i praksis — den undgår patologiske værste tilfælde, som en modstander kunne konstruere for strategier med fast pivot.
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]Medianen af tre som pivot
En anden pivotstrategi er at vælge medianen af det første, midterste og sidste element. Det undgår adfærd i værste tilfælde på sorterede eller omvendt sorterede inddata (de mest almindelige inddata, som en modstander kan konstruere), samtidig med at omkostningen ved generering af tilfældige tal undgås. Mange implementeringer i produktion bruger median-af-tre eller ninther (medianen af tre medianer) til store arrays og falder tilbage til indsættelsessortering for små underarrays under en tærskel på ~10 elementer.
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)Det hollandske flag: tredelt partitionering
Standardpartitionering placerer elementer, der er mindre end pivotten, til venstre og større elementer til højre, men elementer, der er lig med pivotten, bliver spredt ud. Tredelt partitionering (det hollandske flag) opretter tre områder: <pivot, ==pivot, >pivot. Det er afgørende for arrays med mange dubletter — hvor standard-quicksort forringes til O(n²), mens tredelt quicksort giver O(n) for inddata, hvor alle værdier er ens.
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: det k-te mindste i O(n)
Quickselect bruger quicksorts partitioneringstrin til at finde det k-te mindste element i gennemsnitlig O(n)-tid uden at sortere alt. Efter partitioneringen står pivotten på sin endelige placering p. Hvis p == k, returneres arr[p]. Hvis k < p, rekurseres der på den venstre partition; hvis k > p, rekurseres der på den højre. I gennemsnit halverer hvert rekursionskald problemet: 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)Quicksorts pladskompleksitet
Quicksort kaldes ’in-place’, men bruger i gennemsnit O(log n) stakplads til rekursion (én ramme pr. niveau i rekursionstræet). I værste tilfælde er stakdybden O(n). For at garantere O(log n) stakplads i værste tilfælde skal du altid rekursere på den mindre partition først og bruge haleoptimering til den større partition. Pythons rekursionsgrænse gør meget dybe quicksort-rekursioner risikable — det er værd at nævne ved jobsamtaler.
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 + 1Sammenligning af sorteringsalgoritmer
Sammenfat din viden:
- Quicksort: forventet O(n log n), O(n²) i værste tilfælde, O(log n) plads, ustabil, hurtigst i praksis for tilfældige data
- Mergesort: garanteret O(n log n), O(n) plads, stabil, bedst til sammenkædede lister og ekstern sortering
- Heapsort: garanteret O(n log n), O(1) plads, ustabil, langsommere i praksis på grund af cache-misses
- Indsættelsessortering: O(n) i bedste tilfælde, ideel til små n eller næsten sorterede data
# 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: kombination af alle tre
Introsort (brugt i C++ STL std::sort) kombinerer quicksort, heapsort og indsættelsessortering: start med randomiseret quicksort; hvis rekursionsdybden overstiger 2 log n (hvilket indikerer en dårlig pivotsekvens), skiftes der til heapsort for at garantere O(n log n); brug indsættelsessortering til underarrays med færre end 16 elementer. Det giver O(n log n) i værste tilfælde sammen med quicksorts hastighed i gennemsnit og indsættelsessorteringens effektivitet på små underarrays.
# 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]))Hurtigt tjek
Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du: quicksort opdeler arrayet på stedet omkring en pivot og rekurserer på hver side, hvilket giver forventet O(n log n)-tid med O(log n) stakplads — og gør den hurtigere i praksis end mergesort på tilfældige data, værste tilfælde O(n²) opstår på sorterede inddata med en fast pivot og undgås ved randomiseret pivotvalg eller median-af-tre, og tredelt partitionering håndterer ens elementer effektivt, mens quickselect udvider partitionsidéen til at finde det k-te mindste element i gennemsnitlig O(n)-tid uden fuld sortering. Dernæst undersøger vi sorteringer uden sammenligning og Pythons indbyggede sortering.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Quick sort og valg af pivot” gratis?
Ja — hele teksten til “Quick sort og valg af pivot” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Quick sort og valg af pivot”?
Opbyg quick sort med Lomuto- og Hoare-partitionering, og gennemgå worst-case O(n²) samt hvordan randomiseret pivotvalg afhjælper det. Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Quick sort og valg af pivot”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Bubble sort og insertion sort
- Merge sort: opdel, sortér, flet
- Quick sort og valg af pivot
- Sortering uden sammenligning og Pythons sort()