Quick sort og valg av pivot
Bygg quick sort med Lomuto- og Hoare-partisjonering, og se hvordan tilfeldig pivotvalg reduserer risikoen ved verst tenkelig O(n²).
Quick sort og valg av pivot er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 3 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Quick sort: del-og-hersk in-place
Quick sort er den mest brukte sorteringsalgoritmen i praksis. I motsetning til merge sort sorterer den in-place uten å allokere ekstra tabeller. Kjerneideen er å velge et pivot-element, partisjonere tabellen slik at alle elementer som er mindre enn pivotet kommer før det og alle større elementer etter det, og deretter sortere hver partisjon rekursivt. Partisjoneringen tar O(n) tid, og med et godt pivot er rekursjonsdybden 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-partisjoneringsskjemaet
Lomuto-partisjonering bruker det siste elementet som pivot. En langsom peker i følger grensen for området med elementer som er mindre enn pivotet, mens en rask peker j skanner fremover. Når arr[j] <= pivot, økes i, og arr[i] byttes med arr[j], slik at området med små elementer utvides. Etter skanningen plasseres pivotet på i+1 ved å bytte det med arr[hi]. Metoden er enkel å implementere, men utfører tre ganger så mange bytter som Hoares skjema.
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 partisjoneringsskjema
Hoare-partisjonering bruker to pekere som starter i hver sin ende og beveger seg innover til de krysser hverandre. Pivotet velges (vanligvis det første elementet), og elementer som er mindre enn pivotet flyttes til venstre, mens større elementer flyttes til høyre. Hoares skjema utfører tre ganger færre bytter enn Lomutos og fungerer bedre med like elementer, men pivotet havner ikke på sin endelige plass etter partisjoneringen – derfor kreves det litt annerledes rekursive kall.
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]Verste tilfelle O(n²): Allerede sorterte inndata
Verste tilfelle for quick sort oppstår når pivotet konsekvent er det minste eller største elementet i partisjonen. Med Lomutos pivot fra siste element på en allerede sortert tabell plasserer partisjoneringen alltid 0 elementer til venstre og n-1 til høyre. Rekursjonstreet degenererer da til en kjede med dybde n, noe som gir O(n²) sammenligninger. Derfor er valg av pivot avgjørende, og produksjonsimplementasjoner velger pivotet tilfeldig.
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)/2Tilfeldig pivot: forventet O(n log n)
Ved å velge pivotet jevnt tilfeldig (bytt et tilfeldig element med arr[hi] før partisjoneringen) avtar sannsynligheten for konsekvent å velge dårlige pivoter eksponentielt. Det forventede antallet sammenligninger er 2n ln(n) ≈ 1.39 n log₂(n), noe som gir forventet kjøretid på O(n log n) med overveldende sannsynlighet. Derfor brukes tilfeldig quick sort i praksis – den unngår patologiske verste tilfeller som en motstander kan lage 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 av tre som pivot
En annen pivotstrategi er å velge medianen av det første, midterste og siste elementet. Dette unngår oppførsel i verste tilfelle for sorterte eller omvendt sorterte inndata (de vanligste ugunstige inndataene), samtidig som man unngår kostnaden ved å generere tilfeldige tall. Mange produksjonsimplementasjoner bruker median-av-tre eller ninther (medianen av tre medianer) for store tabeller, og går tilbake til insertion sort for små deltabeller under en terskel på omtrent 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 nederlandske flagget: treveis partisjonering
Standard partisjonering plasserer elementer som er mindre enn pivotet til venstre og større elementer til høyre, men elementer som er lik pivotet blir spredt rundt. Treveis partisjonering (det nederlandske flagget) oppretter tre områder: <pivot, ==pivot, >pivot. Dette er avgjørende for tabeller med mange duplikater – der vanlig quick sort får O(n²), mens treveis quick sort gir O(n) for inndata der alle verdiene er like.
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 minste elementet i O(n)
Quickselect bruker partisjoneringssteget fra quick sort til å finne det k-te minste elementet på O(n) tid i gjennomsnitt, uten å sortere alt. Etter partisjoneringen står pivotet på sin endelige plass p. Hvis p == k, returneres arr[p]. Hvis k < p, utføres rekursjon på den venstre partisjonen; hvis k > p, utføres rekursjon på den høyre. I gjennomsnitt halverer hver rekursjon 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)Plasskompleksitet for quick sort
Quick sort kalles 'in-place', men bruker O(log n) plass i kallestakken i gjennomsnitt (én ramme per nivå i rekursjonstreet). I verste fall blir stakkdybden O(n). For å garantere O(log n) stakkplass i verste fall bør man alltid utføre rekursjon på den mindre partisjonen først og bruke tail-call-optimalisering for den større partisjonen. Pythons rekursjonsgrense gjør svært dype rekursjoner i quick sort risikable – dette er verdt å nevne i intervjuer.
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 av sorteringsalgoritmer
Sammenfatt kunnskapen:
- Quick sort: forventet O(n log n), O(n²) i verste fall, O(log n) plass, ustabil, raskest i praksis for tilfeldige data
- Merge sort: garantert O(n log n), O(n) plass, stabil, best for lenkede lister og ekstern sortering
- Heap sort: garantert O(n log n), O(1) plass, ustabil, tregere i praksis på grunn av cache-misser
- Insertion sort: O(n) i beste tilfelle, ideell for liten n eller nesten sorterte 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: kombinerer alle tre
Introsort (brukt i C++ STL std::sort) kombinerer quick sort, heap sort og insertion sort: start med tilfeldig quick sort; hvis rekursjonsdybden overskrider 2 log n (noe som tyder på en dårlig pivotsekvens), bytt til heap sort for å garantere O(n log n); bruk insertion sort for deltabeller med færre enn 16 elementer. Dette gir O(n log n) i verste fall, med quick sorts hastighet i gjennomsnitt og insertion sorts effektivitet for små deltabeller.
# 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]))Kunnskapssjekk
Test forståelsen av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen har man lært: quick sort partisjonerer in-place rundt et pivot og utfører rekursjon på hver side, noe som gir forventet kjøretid på O(n log n) med O(log n) plass i kallestakken – raskere i praksis enn merge sort for tilfeldige data, verste tilfelle O(n²) oppstår på sorterte inndata med et fast pivot og unngås ved tilfeldig valg av pivot eller median-av-tre, og treveis partisjonering håndterer duplikater effektivt, mens quickselect utvider partisjoneringsideen til å finne det k-te minste elementet på O(n) tid i gjennomsnitt uten full sortering. Neste steg er å utforske sorteringer som ikke bygger på sammenligninger, og Pythons innebygde sortering.
Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 90
- Leksjoner
- 360
Ofte stilte spørsmål
Er leksjonen «Quick sort og valg av pivot» gratis?
Ja – hele teksten i «Quick sort og valg av pivot» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.
Hva lærer jeg i «Quick sort og valg av pivot»?
Bygg quick sort med Lomuto- og Hoare-partisjonering, og se hvordan tilfeldig pivotvalg reduserer risikoen ved verst tenkelig O(n²). Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?
Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 3 av 4.
Hvor lang tid tar leksjonen «Quick sort og valg av pivot»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?
Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.
Alle leksjonene i dette kurset
- Bubble sort og insertion sort
- Merge sort: del, sorter, flett
- Quick sort og valg av pivot
- Sortering uten sammenligning og Pythons sort()