Quick sort ja pivotin valinta
Rakentakaa quick sort Lomuton ja Hoaren osiointimenetelmillä, käsitelkää pahimman tapauksen O(n²)-aikavaativuutta ja selittäkää, miten satunnaistettu pivotin valinta lieventää sitä.
Quick sort ja pivotin valinta on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 3/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Pikalajittelu: paikallaan toimiva hajota ja hallitse
Pikalajittelu on käytännössä laajimmin käytetty lajittelualgoritmi. Toisin kuin lomituslajittelu, se lajittelee paikallaan varaamatta ylimääräisiä taulukoita. Ydinajatus on seuraava: valitaan pivot-alkio, ositetaan taulukko niin, että kaikki pivotia pienemmät alkiot tulevat ennen sitä ja kaikki suuremmat sen jälkeen, ja lajitellaan sitten kumpikin osio rekursiivisesti. Ositusvaihe vie aikaa O(n), ja hyvällä pivotilla rekursion syvyys on 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]Lomuton ositusmenetelmä
Lomuton partitionointi käyttää viimeistä alkiota pivotina. Hidas osoitin i seuraa pivotia pienempien alkioiden alueen rajaa, ja nopea osoitin j käy taulukkoa eteenpäin. Kun arr[j] <= pivot, osoitinta i kasvatetaan ja alkiot arr[i] ja arr[j] vaihdetaan, jolloin pienten alkioiden aluetta laajennetaan. Kun läpikäynti on valmis, pivot sijoitetaan paikkaan i+1 vaihtamalla se alkion arr[hi] kanssa. Menetelmä on helppo toteuttaa, mutta siinä tehdään 3× enemmän vaihtoja kuin Hoaren menetelmässä.
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)Hoaren ositusmenetelmä
Hoaren partitionointi käyttää kahta osoitinta, jotka aloittavat vastakkaisista päistä ja liikkuvat kohti toisiaan, kunnes ne ohittavat toisensa. Menetelmä valitsee pivotin (yleensä ensimmäisen alkion) ja siirtää pivotia pienemmät alkiot vasemmalle ja suuremmat oikealle. Hoaren menetelmä tekee 3× vähemmän vaihtoja kuin Lomuton menetelmä ja toimii paremmin yhtä suurten alkioiden kanssa, mutta pivot ei päädy osituksen jälkeen lopulliseen paikkaansa — siksi tarvitaan hieman erilaiset rekursiiviset kutsut.
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]Huonoin tapaus O(n²): valmiiksi järjestetty syöte
Pikalajittelun huonoin tapaus syntyy, kun pivot on osiossa jatkuvasti pienin tai suurin alkio. Kun Lomuton menetelmä käyttää viimeistä alkiota pivotina valmiiksi järjestetyssä taulukossa, ositus sijoittaa aina 0 alkiota vasemmalle ja n-1 alkiota oikealle: rekursiopuu surkastuu n:n syvyiseksi ketjuksi, jolloin vertailujen määrä on O(n²). Siksi pivotin valinta on ratkaisevan tärkeää ja tuotantototeutukset satunnaistavat pivotin.
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)/2Satunnaistettu pivot: odotusarvoisesti O(n log n)
Kun pivot valitaan tasaisesti satunnaisesti (satunnainen alkio vaihdetaan alkion arr[hi] kanssa ennen ositusta), jatkuvasti huonojen pivotien valitsemisen todennäköisyys pienenee eksponentiaalisesti. Odotettu vertailujen määrä on 2n ln(n) ≈ 1.39 n log₂(n), joten odotettu aikavaativuus on O(n log n) ylivoimaisella todennäköisyydellä. Tämän vuoksi satunnaistettua pikalajittelua käytetään käytännössä — se välttää kiinteän pivotin strategioiden huonoimmat tapaukset, jotka vastustaja voisi tarkoituksellisesti luoda.
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]Kolmen alkion mediaani pivotina
Toinen pivot-strategia on valita ensimmäisen, keskimmäisen ja viimeisen alkion mediaani. Tämä välttää huonoimman tapauksen käyttäytymisen järjestetyillä tai käänteisessä järjestyksessä olevilla syötteillä (yleisimmillä vastustajan luomilla syötteillä) ilman satunnaislukujen tuottamisen kustannuksia. Monissa tuotantototeutuksissa käytetään median-of-three-menetelmää tai ninther-menetelmää suurilla taulukoilla ja vaihdetaan lisäyslajitteluun, kun pienissä alitaulukoissa on alle noin 10 alkiota.
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)Hollannin lippu: kolmijakoinen ositus
Tavallinen ositus sijoittaa pivotia pienemmät alkiot vasemmalle ja suuremmat oikealle, mutta pivotin kanssa yhtä suuret alkiot hajaantuvat. Kolmijakoinen ositus (Hollannin lippu) muodostaa kolme aluetta: <pivot, ==pivot, >pivot. Tämä on ratkaisevan tärkeää taulukoilla, joissa on paljon duplikaatteja — tavallinen pikalajittelu hidastuu tällöin aikavaativuuteen O(n²), kun taas kolmijakoinen pikalajittelu saavuttaa samanarvoisista alkioista koostuvilla syötteillä aikavaativuuden O(n).
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:nnen pienimmän etsiminen ajassa O(n)
Quickselect käyttää pikalajittelun ositusvaihetta k:nnen pienimmän alkion löytämiseen keskimäärin ajassa O(n) ilman koko taulukon lajittelua. Osituksen jälkeen pivot on lopullisessa paikassaan p. Jos p == k, palautetaan arr[p]. Jos k < p, kutsutaan rekursiota vasemmalle osiolle; jos k > p, oikealle osiolle. Keskimäärin jokainen rekursiokutsu puolittaa ongelman: 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)Pikalajittelun tilavaativuus
Pikalajittelua kutsutaan 'paikallaan toimivaksi', mutta rekursio käyttää keskimäärin O(log n) tilaa kutsupinossa (yksi kehys rekursiopuun tasoa kohden). Huonoimmassa tapauksessa pinon syvyys on O(n). O(log n):n suurimman mahdollisen kutsupinotilan takaamiseksi rekursio kannattaa kohdistaa aina ensin pienempään osioon ja käyttää suuremman osion käsittelyssä häntäkutsuoptimointia. Pythonin rekursiorajan vuoksi hyvin syvät pikalajittelurekursiot ovat riskialttiita — tämä kannattaa mainita haastatteluissa.
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 + 1Lajittelualgoritmien vertailu
Kootaan tietonne yhteen:
- Pikalajittelu: odotusarvoisesti O(n log n), huonoimmassa tapauksessa O(n²), tilaa O(log n), epävakaa, käytännössä nopein satunnaisella datalla
- Lomituslajittelu: taattu O(n log n), tilaa O(n), vakaa, paras linkitetyille listoille ja ulkoiseen lajitteluun
- Kekolajittelu: taattu O(n log n), tilaa O(1), epävakaa, käytännössä hitaampi välimuistihäiriöiden vuoksi
- Lisäyslajittelu: parhaassa tapauksessa O(n), ihanteellinen pienelle n:lle tai lähes järjestetylle datalle
# 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: kaikkien kolmen yhdistäminen
Introsort (jota käytetään C++ STL:n std::sort-toiminnossa) yhdistää pikalajittelun, kekolajittelun ja lisäyslajittelun: aloitetaan satunnaistetulla pikalajittelulla; jos rekursiosyvyys ylittää arvon 2 log n (mikä osoittaa huonojen pivotien sarjan), vaihdetaan kekolajitteluun, joka takaa aikavaativuuden O(n log n); alle 16 alkion alitaulukoille käytetään lisäyslajittelua. Näin saadaan huonoimmassakin tapauksessa O(n log n) pikalajittelun keskimääräisen tapauksen nopeudella ja lisäyslajittelun tehokkuudella pienissä alitaulukoissa.
# 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]))Pikatesti
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheiden ymmärtämistä.
Oppitunnin kertaus
Tässä oppitunnissa opitte, että pikalajittelu osittaa taulukon paikallaan pivotin ympärille ja kutsuu itseään rekursiivisesti kummallekin puolelle, jolloin odotettu aikavaativuus on O(n log n) ja kutsupinon tila O(log n) — käytännössä se on satunnaisella datalla lomituslajittelua nopeampi, huonoin tapaus O(n²) syntyy järjestetyllä syötteellä kiinteää pivotia käytettäessä, ja se vältetään satunnaistetulla pivotin valinnalla tai kolmen alkion mediaanilla ja kolmijakoinen ositus käsittelee duplikaatit tehokkaasti, ja quickselect laajentaa ositusidean k:nnen pienimmän alkion löytämiseen keskimäärin ajassa O(n) ilman koko taulukon lajittelua. Seuraavaksi tutustumme vertailuihin perustumattomiin lajittelumenetelmiin ja Pythonin sisäiseen lajitteluun.
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Quick sort ja pivotin valinta” ilmainen?
Kyllä – oppitunnin ”Quick sort ja pivotin valinta” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Quick sort ja pivotin valinta”?
Rakentakaa quick sort Lomuton ja Hoaren osiointimenetelmillä, käsitelkää pahimman tapauksen O(n²)-aikavaativuutta ja selittäkää, miten satunnaistettu pivotin valinta lieventää sitä. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 3/4.
Kuinka kauan ”Quick sort ja pivotin valinta”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Bubble sort ja insertion sort
- Merge sort: jaa, lajittele, yhdistä
- Quick sort ja pivotin valinta
- Vertailusta riippumattomat lajittelut ja Pythonin sort()