Vertailusta riippumattomat lajittelut ja Pythonin sort()
Tutustukaa laskenta- ja radix-lajitteluun kokonaislukutaulukoilla ja ymmärtäkää, miten Pythonin Timsort toimii sisäisesti built-in sort -kutsuissa.
Vertailusta riippumattomat lajittelut ja Pythonin sort() on ilmainen DSA Interview Prep-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea tästä oppimispolusta kokonaan mitkä tahansa 3 oppituntia ilmaiseksi — sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä käytännön harjoittelun sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. Oppitunti kuuluu DSA Interview Prep-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Vertailujen O(n log n) alaraja
Kaikki lajittelualgoritmit, jotka selvittävät järjestyksen ainoastaan alkioiden vertailujen avulla, tarvitsevat huonoimmassa tapauksessa vähintään Ω(n log n) vertailua. Tämä voidaan osoittaa päätöspuuargumentilla: n alkion lajittelu edellyttää n! mahdollisen järjestyksen erottamista toisistaan. Binäärinen päätöspuu (jonka jokainen solmu on vertailu) tarvitsee vähintään log₂(n!) ≈ n log₂(n) tasoa. Tämän rajan alittamiseksi tarvitaan alkioista lisätietoa — esimerkiksi tieto siitä, että ne ovat rajoitettuja kokonaislukuja.
import math
for n in [5, 10, 100, 1000]:
lower_bound = n * math.log2(n)
factorial_log = sum(math.log2(i) for i in range(1, n+1))
print(f'n={n}: n*log2(n)={lower_bound:.1f}, log2(n!)={factorial_log:.1f}')
# n log n is a tight bound on comparison-based sortingLaskentalajittelu: lajittelu esiintymistiheyden mukaan
Laskentalajittelu laskee kunkin arvon esiintymistiheyden ja muodostaa sitten järjestetyn taulukon uudelleen laskureiden perusteella. Se edellyttää, että arvojen alue [0, k) tunnetaan etukäteen. Aikavaativuus on O(n + k) ja tilavaativuus O(k). Kun k on pieni suhteessa n:ään (esimerkiksi lajitellaan ikiä väliltä 0–120 tai yksinumeroisia lukuja), laskentalajittelu päihittää kaikki vertailuihin perustuvat lajittelumenetelmät. Kun k on suuri, O(k):n tilakustannus tekee menetelmästä epäkäytännöllisen.
def counting_sort(arr, k=None):
if not arr: return []
if k is None: k = max(arr) + 1
count = [0] * k
for n in arr:
count[n] += 1
result = []
for val, freq in enumerate(count):
result.extend([val] * freq)
return result
arr = [4, 2, 2, 8, 3, 3, 1]
print(counting_sort(arr)) # [1, 2, 2, 3, 3, 4, 8]
# O(n + k) where k = 9 (max value + 1)Vakaa counting sort kumulatiivisilla lukumäärillä
Vakaassa counting sort -lajittelussa (tärkeä, kun olioita lajitellaan avaimen perusteella) lasketaan kumulatiiviset lukumäärät niin, että cum[v] antaa arvon v aloituskohdan tulosteessa. Käykää syötejoukko läpi oikealta vasemmalle, sijoittakaa kukin alkio kohtaan cum[key] - 1 ja pienentäkää kyseistä kohtaa. Näin syntyy vakaa lajittelu: saman avaimen alkiot säilyttävät alkuperäisen keskinäisen järjestyksensä.
def counting_sort_stable(arr, k):
count = [0] * k
for n in arr: count[n] += 1
# Cumulative counts: count[v] = first position for value v
for i in range(1, k): count[i] += count[i-1]
output = [0] * len(arr)
# Fill from right to maintain stability
for n in reversed(arr):
count[n] -= 1
output[count[n]] = n
return output
print(counting_sort_stable([4,2,2,8,3,3,1], 9))
# [1, 2, 2, 3, 3, 4, 8]Radix sort: lajittele numero kerrallaan
Radix sort lajittelee kokonaisluvut numero kerrallaan vähiten merkitsevästä numerosta (LSD) eniten merkitsevään (MSD) käyttäen joka kohdassa vakaata lajittelua, kuten counting sortia. Kun d läpikäyntiä, yksi kutakin numeroa kohden, on tehty, taulukko on kokonaan lajiteltu. Aikavaativuus on O(d × (n + k)), missä d = numeroiden määrä ja k = kantaluku (yleensä 10). Kun lajitellaan n:ää ylärajalla W rajoitettua kokonaislukua, d = log_k(W), joten kokonaisvaativuus on O(n log_k(W)).
def radix_sort(arr):
if not arr: return []
max_val = max(arr)
exp = 1 # current digit position (1, 10, 100, ...)
while max_val // exp > 0:
arr = counting_sort_by_digit(arr, exp)
exp *= 10
return arr
def counting_sort_by_digit(arr, exp):
n = len(arr)
output = [0] * n
count = [0] * 10
for n_ in arr: count[(n_ // exp) % 10] += 1
for i in range(1, 10): count[i] += count[i-1]
for n_ in reversed(arr):
d = (n_ // exp) % 10
count[d] -= 1
output[count[d]] = n_
return output
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]Bucket sort: jaa alkiot lokeroihin
Bucket sort jakaa alkiot arvoalueen perusteella kiinteään määrään lokeroita, lajittelee kunkin lokeron (pienille lokeroille esimerkiksi insertion sortilla) ja yhdistää lokerot. Tasaisesti jakautuneella datalla välillä [0, 1) n lokeroa tuottaa keskimääräisen O(n):n aikavaativuuden. Keskimääräinen aikavaativuus on O(n + k) ja pahimmassa tapauksessa O(n)², jos kaikki alkiot päätyvät samaan lokeroon. Menetelmä on hyödyllisin, kun datan jakauma tunnetaan ja se on likimain tasainen.
def bucket_sort(arr):
if not arr: return []
n = len(arr)
min_v, max_v = min(arr), max(arr)
if min_v == max_v: return arr[:]
buckets = [[] for _ in range(n)]
# Map each value to a bucket index
for v in arr:
idx = int((v - min_v) / (max_v - min_v + 1e-9) * n)
idx = min(idx, n - 1)
buckets[idx].append(v)
result = []
for bucket in buckets:
bucket.sort() # insertion sort for small buckets
result.extend(bucket)
return result
print(bucket_sort([0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21]))
# sorted listPythonin Timsort konepellin alla
Pythonin sorted() ja list.sort() käyttävät Timsortia, jonka Tim Peters suunnitteli vuonna 2002. Timsort on merge sortin ja insertion sortin yhdistelmä. Se etsii ”luonnollisia jaksoja” (valmiiksi lajiteltuja osajaksoja) ja käyttää insertion sortia enintään 64 alkion jaksojen muodostamiseen. Sen jälkeen se yhdistää jaksot merge sortin tapaan useiden optimointien avulla: galloping-menetelmällä (alkioiden ohittaminen lohkoittain, kun toinen jakso on hallitseva) ja jaksojen pituuksien pinoamisella.
# Timsort properties:
# - Stable
# - O(n log n) worst case
# - O(n) best case (data already sorted)
# - O(n) auxiliary space
# - Highly optimised for real-world data with runs
import time
# Nearly sorted data: Timsort is extremely fast
nearly_sorted = list(range(10000))
nearly_sorted[-1] = 0 # one mis-placed element
t = time.perf_counter()
not_used = sorted(nearly_sorted)
elapsed = time.perf_counter() - t
print(f'Timsort on nearly-sorted n=10000: {elapsed*1000:.3f} ms')Pythonin sort() vs sorted(): keskeiset erot
list.sort() lajittelee paikallaan, palauttaa None-arvon ja toimii vain listoilla. sorted(iterable) toimii millä tahansa iteroitavalla kohteella (monikoilla, generaattoreilla ja sanakirjoilla) ja palauttaa uuden listan. Molemmat hyväksyvät key- ja reverse-parametrit. Yleinen virhe on tallentaa lst.sort()-kutsun palautusarvo muuttujaan ja ihmetellä, miksi sen arvo on None. Käyttäkää aina sorted()-funktiota, kun tarvitsette lajitellun version ja haluatte säilyttää alkuperäisen.
nums = [3, 1, 4, 1, 5, 9]
# in-place: returns None
result = nums.sort()
print(result) # None (common bug!)
print(nums) # [1, 1, 3, 4, 5, 9] (modified)
nums2 = [3, 1, 4, 1, 5, 9]
# out-of-place: returns new list
result2 = sorted(nums2)
print(result2) # [1, 1, 3, 4, 5, 9]
print(nums2) # [3, 1, 4, 1, 5, 9] (unchanged)Mukautetut lajitteluavaimet työhaastatteluissa
Pythonin sort hyväksyy key-funktion, joka suoritetaan kerran kutakin alkiota kohden (toisin kuin C:n vertailufunktio, jota kutsutaan jokaiselle parille). Yleisiä haastatteluissa käytettäviä lajitteluavaimia ovat len merkkijonon pituudelle, lambda x: -x laskevaan järjestykseen, lambda x: (x[1], x[0]) usean avaimen lajitteluun ja str.lower kirjainkoosta riippumattomaan lajitteluun. Pythonin lajittelu on taatusti vakaa, joten usean avaimen lajittelu toimii oikein.
# Sort by length, then alphabetically
words = ['banana', 'fig', 'apple', 'date', 'kiwi']
print(sorted(words, key=lambda w: (len(w), w)))
# ['fig', 'date', 'kiwi', 'apple', 'banana']
# Sort integers as strings (largest concatenation first)
nums = [3, 30, 34, 5, 9]
print(sorted(map(str, nums), key=lambda a: a*10, reverse=True))
# ['9', '5', '34', '3', '30'] => '9534330'
# Descending sort
print(sorted([3,1,4,1,5], reverse=True)) # [5,4,3,1,1]Milloin kutakin lajittelua käytetään työhaastattelussa
Valitkaa tilanteeseen sopiva lajittelumenetelmä:
- Käyttäkää Pythonin sorted()/list.sort(): oletusvalinta kaikkiin haastattelutehtäviin — Timsort on optimaalinen
- Counting sort: kun arvot ovat pieniä, rajatulla alueella olevia kokonaislukuja (0–k, k pieni)
- Radix sort: kun lajitellaan paljon kokonaislukuja, joiden bittileveys tai numeroiden määrä tunnetaan
- Bucket sort: kun lajiteltavat liukuluvut jakautuvat tasaisesti tunnetulle arvoalueelle
- Toteuttakaa merge sort: kun pyydetään koodaamaan vakaa O(n log n):n lajittelu alusta alkaen
# Problem: sort array of 0s, 1s, 2s efficiently
# Counting sort: O(n), O(1) space (k=3 is tiny)
def sort_012(arr):
count = [0, 0, 0]
for n in arr:
count[n] += 1
i = 0
for val in range(3):
for _ in range(count[val]):
arr[i] = val; i += 1
arr = [2, 0, 2, 1, 1, 0]
sort_012(arr)
print(arr) # [0, 0, 1, 1, 2, 2]Lajittelu ilman täydellistä lajittelua: top-k kekoa käyttäen
Monissa haastattelutehtävissä pyydetään ”lajittelun kaltaisia” tuloksia ilman koko joukon lajittelua. Top-k-alkioiden etsiminen minimikeolla, jonka koko on k, toimii ajassa O(n log k) — nopeammin kuin O(n log n), kun k << n. K:nneksi suurimman alkion etsiminen quickselectilla toimii keskimäärin ajassa O(n). Mediaanin etsiminen kahden keon menetelmällä vie O(log n) aikaa lisäystä kohden. Nämä osittaisen lajittelun menetelmät kannattaa tuntea, sillä ne ovat nopeampia vaihtoehtoja koko joukon lajittelulle.
import heapq
# Top-k with heap: O(n log k)
def top_k(nums, k):
return heapq.nlargest(k, nums) # uses heap of size k internally
print(top_k([3,2,1,5,6,4], 2)) # [6, 5]
# kth largest: quickselect O(n) average
import random
def kth_largest(nums, k):
def _select(lo, hi, target):
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]
nums[i+1],nums[hi]=nums[hi],nums[i+1]
p = i + 1
if p == target: return nums[p]
return _select(lo, p-1, target) if target < p else _select(p+1, hi, target)
return _select(0, len(nums)-1, k-1)
print(kth_largest([3,2,1,5,6,4], 2)) # 5Lajittelun vakaus usean avaimen lajittelussa
Vakaus mahdollistaa oikean usean avaimen lajittelun: lajitelkaa ensin toissijaisen avaimen mukaan vakaasti ja sitten ensisijaisen avaimen mukaan vakaasti. Toissijaisen avaimen mukainen järjestys säilyy, kun ensisijaisessa avaimessa on sama arvo. Tätä tekniikkaa käytetään tietokannoissa (ORDER BY col1, col2) ja radix sortissa (jokaisen numeron käsittelykierroksen on oltava vakaa, jotta koko algoritmi toimii oikein). Pythonin lajittelu on aina vakaa, joten tämä malli toimii luotettavasti.
data = [
('Alice', 'Math', 90),
('Bob', 'Science', 85),
('Carol', 'Math', 90),
('Dave', 'Science', 90),
]
# Sort by score DESC, then by subject ASC (for ties)
# Step 1: sort by subject (secondary)
data.sort(key=lambda x: x[1])
# Step 2: sort by score DESC (primary, stable)
data.sort(key=lambda x: x[2], reverse=True)
for row in data:
print(row)
# All score=90 rows: Math before Science (preserved from step 1)Pikatarkistus
Testatkaa tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -aiheen käsitteiden ymmärtämistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että vertailuun perustuvien lajittelujen alaraja on O(n log n) — tämän rajan rikkominen edellyttää vertailuihin perustumattomia tietoja, kuten rajatulla alueella olevia kokonaislukuja, counting sort saavuttaa O(n + k):n laskemalla frekvenssit, radix sort käsittelee numerot kokonaisvaativuudella O(d × (n + k)) ja bucket sort hyödyntää tasaista jakaumaa saavuttaakseen keskimäärin O(n):n sekä Pythonin Timsort on käytännöllinen oletusvalinta — vakaa, pahimmassa tapauksessa O(n log n), parhaassa tapauksessa O(n) ja todellisella datalla nopeampi kuin mikään käsin koodattu vaihtoehto. Seuraavaksi perehdymme klassiseen binäärihakuun.
Opi Python 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
- 30
- Oppitunnit
- 120
Usein kysytyt kysymykset
Onko oppitunti ”Vertailusta riippumattomat lajittelut ja Pythonin sort()” ilmainen?
Kyllä — voit lukea täällä verkossa kokonaan ilmaiseksi mitkä tahansa DSA Interview Prep-oppimispolun 3 oppituntia, myös oppitunnin “Vertailusta riippumattomat lajittelut ja Pythonin sort()”. Sen jälkeen CoddyKit PRO avaa kaikki oppitunnit sekä interaktiiviset harjoitukset sisäänrakennetulla koodieditorilla ja ympäri vuorokauden toimivalla tekoälytuutorilla. DSA Interview Prep-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Vertailusta riippumattomat lajittelut ja Pythonin sort()”?
Tutustukaa laskenta- ja radix-lajitteluun kokonaislukutaulukoilla ja ymmärtäkää, miten Pythonin Timsort toimii sisäisesti built-in sort -kutsuissa. Harjoittelet DSA Interview Prep-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni DSA Interview Prep-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin DSA Interview Prep-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Vertailusta riippumattomat lajittelut ja Pythonin sort()”-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ä DSA Interview Prep-oppitunnilla?
Kyllä. Jokainen DSA Interview Prep-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()