Sortering uten sammenligning og Pythons sort()
Utforsk counting sort og radix sort for heltallsarrayer, og forstå hvordan Pythons Timsort fungerer internt ved kall til den innebygde sort-funksjonen.
Sortering uten sammenligning og Pythons sort() er en gratis leksjon i DSA Interview Prep på CoddyKit. Dette er leksjon 4 av 4. Du kan lese valgfritt 3 leksjoner fra denne læringsstien gratis i sin helhet – deretter låser CoddyKit PRO opp alle leksjoner, samt praktisk øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i DSA Interview Prep, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Den nedre O(n log n)-grensen for sammenligninger
Enhver sorteringsalgoritme som bestemmer rekkefølgen kun gjennom sammenligninger av elementer, krever minst Ω(n log n) sammenligninger i verste fall. Dette bevises med beslutningstreargumentet: Sortering av n elementer krever at man skiller mellom n! mulige rekkefølger. Et binært beslutningstre (der hver node er en sammenligning) trenger minst log₂(n!) ≈ n log₂(n) nivåer. For å bryte denne grensen trenger man tilleggsinformasjon om elementene – for eksempel at de er heltall innenfor et begrenset område.
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 sortingCounting sort: sorter etter frekvens
Counting sort fungerer ved å telle frekvensen til hver verdi og deretter bygge den sorterte tabellen på nytt ut fra opptellingene. Algoritmen forutsetter at verdiområdet [0, k) er kjent på forhånd. Tidskompleksiteten er O(n + k), og plasskompleksiteten er O(k). For små k sammenlignet med n (for eksempel ved sortering av aldre fra 0-120 eller ensifrede tall) er counting sort raskere enn alle sammenligningsbaserte sorteringer. For store k gjør plasskostnaden på O(k) algoritmen upraktisk.
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)Stabil counting sort med kumulative tellinger
For en stabil counting sort (viktig når objekter sorteres etter en nøkkel), beregnes kumulative tellinger slik at cum[v] angir startposisjonen til verdien v i resultatet. Gå gjennom input-arrayet fra høyre mot venstre, plasser hvert element på posisjonen cum[key] - 1 og reduser denne posisjonen. Dette gir en stabil sortering – elementer med samme nøkkel beholder sin opprinnelige innbyrdes rekkefølge.
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: sorter siffer for siffer
Radix sort sorterer heltall siffer for siffer, fra det minst signifikante sifferet (LSD) til det mest signifikante (MSD), ved hjelp av en stabil sortering (for eksempel counting sort) ved hver sifferposisjon. Etter d passeringer (én for hvert siffer) er arrayet fullstendig sortert. Tidskompleksitet: O(d × (n + k)), der d = antall siffer og k = base (vanligvis 10). For n heltall begrenset av W er d = log_k(W), noe som gir O(n log_k(W)) totalt.
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: fordel i bøtter
Bucket sort fordeler elementer i et fast antall bøtter basert på verdiområdet, sorterer hver bøtte (med insertion sort for små bøtter) og setter dem sammen. For jevnt fordelte data i [0, 1) gir n bøtter O(n) i gjennomsnittlig kjøretid. Kjøretid: O(n + k) i gjennomsnitt, O(n²) i verste fall (alle elementene havner i én bøtte). Mest nyttig når datafordelingen er kjent og omtrent jevn.
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 listTimsort i Python under panseret
Pythons sorted() og list.sort() bruker Timsort, som ble utviklet av Tim Peters i 2002. Timsort er en kombinasjon av merge sort og insertion sort. Algoritmen leter etter «naturlige sekvenser» (delsekvenser som allerede er sortert) og bruker insertion sort til å bygge sekvenser på opptil 64 elementer. Deretter slår den sammen sekvensene ved hjelp av merge sort med flere optimaliseringer: galloping (hopper over mange elementer samtidig når én sekvens dominerer) og stabling av sekvenslengder.
# 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')Pythons sort() kontra sorted(): viktige forskjeller
list.sort() sorterer på stedet, returnerer None og fungerer bare på lister. sorted(iterable) fungerer med alle iterables (tupler, generatorer og ordbøker) og returnerer en ny liste. Begge godtar parameterne key og reverse. En vanlig feil er å tilordne returverdien fra lst.sort() til en variabel og lure på hvorfor den er None. Bruk alltid sorted() når du trenger den sorterte versjonen og vil beholde originalen.
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)Egendefinerte sorteringsnøkler i intervjuer
Pythons sortering godtar en key-funksjon som evalueres én gang per element (i motsetning til C sin komparator, som kalles for hvert par). Vanlige sorteringsnøkler i intervjuer er len for strenglengde, lambda x: -x for synkende rekkefølge, lambda x: (x[1], x[0]) for sortering med flere nøkler og str.lower for sortering uten hensyn til store og små bokstaver. Pythons sortering er garantert stabil, så sortering med flere nøkler fungerer korrekt.
# 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]Når du bør bruke de ulike sorteringsalgoritmene i intervjuer
Velg riktig sortering ut fra situasjonen:
- Bruk Pythons sorted()/list.sort(): standardvalget for alle intervjuproblemer – Timsort er optimal
- Counting sort: når verdiene er begrensede, små heltall (0 til k, der k er liten)
- Radix sort: når du sorterer mange heltall med kjent bitbredde eller kjent antall siffer
- Bucket sort: når dataene er jevnt fordelte flyttall i et kjent område
- Implementer merge sort: når du blir bedt om å skrive en stabil sortering med O(n log n) fra grunnen av
# 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]Sorter uten sortering: Top-K med en heap
Mange intervjuproblemer ber om «sorteringslignende» resultater uten at en fullstendig sortering er nødvendig. Hvis du skal finne de k største elementene, bruker en min-heap med størrelse k O(n log k) – raskere enn O(n log n) når k << n. For å finne det k-te største elementet har quickselect O(n) gjennomsnittlig kjøretid. For å finne medianen bruker en løsning med to heap-er O(log n) per innsetting. Det er verdt å kjenne til disse metodene for delvis sortering som raskere alternativer til full sortering.
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)) # 5Stabilitet ved sortering med flere nøkler
Stabilitet muliggjør korrekt sortering med flere nøkler: sorter først etter sekundærnøkkelen (stabilt), og deretter etter primærnøkkelen (stabilt). Rekkefølgen etter sekundærnøkkelen bevares for elementer med samme primærnøkkel. Denne teknikken brukes i databaser (ORDER BY col1, col2) og i radix sort (hver sifferpassering må være stabil for at algoritmen som helhet skal bli korrekt). Pythons sortering er alltid stabil, så dette mønsteret fungerer pålitelig.
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)Hurtigsjekk
Test forståelsen din av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Leksjonsoppsummering
I denne leksjonen lærte du: sammenligningsbaserte sorteringer har en nedre grense på O(n log n) – for å bryte denne grensen kreves ikke-sammenligningsbasert informasjon, for eksempel begrensede heltall, counting sort oppnår O(n + k) ved å telle frekvenser, radix sort behandler siffer med totalt O(d × (n + k)), og bucket sort utnytter jevn fordeling for O(n) i gjennomsnitt, og Pythons Timsort er standardvalget i praksis – stabil, O(n log n) i verste fall, O(n) i beste fall og raskere enn ethvert håndkodet alternativ for reelle data. Neste gang skal vi lære klassisk binærsøk.
Lær deg Python 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
- 30
- Leksjoner
- 120
Ofte stilte spørsmål
Er leksjonen «Sortering uten sammenligning og Pythons sort()» gratis?
Ja – du kan lese valgfritt 3 av leksjonene i læringsstien DSA Interview Prep, inkludert «Sortering uten sammenligning og Pythons sort()», gratis i sin helhet her på nettet. Deretter låser CoddyKit PRO opp alle leksjoner, samt interaktiv øving med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Kurset i DSA Interview Prep inneholder totalt 4 leksjoner.
Hva lærer jeg i «Sortering uten sammenligning og Pythons sort()»?
Utforsk counting sort og radix sort for heltallsarrayer, og forstå hvordan Pythons Timsort fungerer internt ved kall til den innebygde sort-funksjonen. Du øver på DSA Interview Prep 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 DSA Interview Prep?
Ingen tidligere erfaring er nødvendig. DSA Interview Prep 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 4 av 4.
Hvor lang tid tar leksjonen «Sortering uten sammenligning og Pythons sort()»?
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 DSA Interview Prep-leksjonen?
Ja. Alle DSA Interview Prep-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()