Sortering uden sammenligning og Pythons sort()
Udforsk counting sort og radix sort for heltalsarrays, og forstå, hvordan Pythons Timsort fungerer internt ved kald til den indbyggede sort.
Sortering uden sammenligning og Pythons sort() er en gratis DSA Interview Prep-lektion på CoddyKit. Dette er lektion 4 af 4. Du kan læse alle 3 lektioner i dette læringsspor gratis i deres fulde længde — derefter låser CoddyKit PRO alle lektioner op samt praktiske øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. Den er en del af læringsforløbet i DSA Interview Prep, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Den nedre grænse O(n log n) for sammenligninger
Enhver sorteringsalgoritme, der kun bestemmer rækkefølgen gennem sammenligninger af elementer, kræver mindst Ω(n log n) sammenligninger i værste tilfælde. Det bevises med beslutningstræsargumentet: Sortering af n elementer kræver, at man skelner mellem n! mulige rækkefølger. Et binært beslutningstræ (hvor hver knude er en sammenligning) skal have mindst log₂(n!) ≈ n log₂(n) niveauer. For at bryde denne grænse har vi brug for yderligere oplysninger om elementerne — f.eks. at de er heltal inden for et begrænset interval.
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 sortingTællesortering: sortér efter hyppighed
Tællesortering fungerer ved at tælle hyppigheden af hver værdi og derefter rekonstruere det sorterede array ud fra tællingerne. Den kræver, at intervallet [0, k) for værdierne er kendt på forhånd. Tidskompleksitet: O(n + k); pladskompleksitet: O(k). For små k i forhold til n (f.eks. ved sortering af aldre fra 0-120 eller enkeltcifrede tal) overgår tællesortering alle sammenligningssorteringer. For store k gør pladsomkostningen på O(k) den 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 tællesortering med kumulative tællinger
Ved stabil tællesortering (vigtigt, når objekter sorteres efter en nøgle) beregner du kumulative tællinger, så cum[v] angiver startpositionen for værdien v i resultatet. Gennemgå inputarrayet fra højre mod venstre, placér hvert element på position cum[key] - 1, og dekrementér positionen. Det giver en stabil sortering — elementer med samme nøgle står i deres oprindelige indbyrdes rækkefø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]Radixsortering: Sortér ciffer for ciffer
Radixsortering sorterer heltal ciffer for ciffer, fra det mindst betydende ciffer (LSD) til det mest betydende (MSD), ved hjælp af en stabil sortering (f.eks. tællesortering) ved hver cifferposition. Efter d gennemløb (ét pr. ciffer) er arrayet fuldt sorteret. Tidskompleksiteten er O(d × (n + k)), hvor d = antal cifre, og k = grundtal (normalt 10). For n heltal, der er begrænset af W, er d = log_k(W), hvilket giver O(n log_k(W)) i alt.
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]Spandsortering: Fordel i spande
Spandsortering fordeler elementer i et fast antal spande baseret på værdiområdet, sorterer hver spand (med indsættelsessortering for små spande) og sammenkæder dem. Ved ensartet fordelte data i [0, 1) giver n spande en gennemsnitlig tidskompleksitet på O(n). Tidskompleksiteten er O(n + k) i gennemsnit og O(n²) i værste fald (hvis alle elementer ender i én spand). Metoden er mest nyttig, når datafordelingen er kendt og tilnærmelsesvis ensartet.
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 listPythons Timsort under motorhjelmen
Pythons sorted() og list.sort() bruger Timsort, som Tim Peters udviklede i 2002. Timsort er en hybrid af flette- og indsættelsessortering. Algoritmen leder efter »naturlige sekvenser« (delsekvenser, der allerede er sorterede) og bruger indsættelsessortering til at opbygge sekvenser på op til 64 elementer. Derefter fletter den sekvenserne ved hjælp af flettesortering med flere optimeringer: gallopering (hvor elementer springes over i større blokke, når én sekvens dominerer) og stabling af sekvenser efter deres længde.
# 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(): Vigtige forskelle
list.sort() sorterer på stedet, returnerer None og fungerer kun på lister. sorted(iterable) fungerer på enhver itererbar værdi (tupler, generatorer og ordbøger) og returnerer en ny liste. Begge accepterer parametrene key og reverse. En almindelig fejl er at tildele returværdien fra lst.sort() til en variabel og undre sig over, hvorfor den er None. Brug altid sorted(), når du har brug for den sorterede version og vil bevare 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)Brugerdefinerede sorteringsnøgler til jobsamtaler
Pythons sortering accepterer en key-funktion, der evalueres én gang pr. element (i modsætning til Cs sammenligningsfunktion, som kaldes for hvert par). Almindelige sorteringsnøgler til jobsamtaler er len for strenglængde, lambda x: -x for faldende rækkefølge, lambda x: (x[1], x[0]) til sortering efter flere nøgler og str.lower til sortering uden forskel på store og små bogstaver. Pythons sortering er garanteret stabil, så sortering efter flere nøgler 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]Hvornår du skal bruge de forskellige sorteringer til jobsamtaler
Vælg den rigtige sortering til situationen:
- Brug Pythons sorted()/list.sort(): standardvalget til alle interviewopgaver — Timsort er optimal
- Tællesortering: når værdierne er små heltal inden for et begrænset område (0 til k, hvor k er lille)
- Radixsortering: når du sorterer mange heltal med en kendt bitbredde eller et kendt antal cifre
- Spandsortering: når data består af ensartet fordelte kommatal i et kendt område
- Implementér flettesortering: når du bliver bedt om at kode en stabil sortering med O(n log n) fra bunden
# 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]Sortér uden sortering: Top-k med en heap
Mange interviewopgaver beder om »sorteringslignende« resultater uden at kræve en fuld sortering. Hvis du skal finde de k største elementer, kører en min-heap med k elementer i O(n log k) — hurtigere end O(n log n), når k << n. Hvis du skal finde det k-te største element, har quickselect en gennemsnitlig tidskompleksitet på O(n). Hvis du skal finde medianen, tager tilgangen med to heaps O(log n) pr. indsættelse. Det er værd at kende disse delvise sorteringer som hurtigere alternativer til fuld 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)) # 5Sorteringsstabilitet ved sortering efter flere nøgler
Stabilitet gør korrekt sortering efter flere nøgler mulig: Sortér først efter den sekundære nøgle (stabilt) og derefter efter den primære nøgle (stabilt). Den sekundære rækkefølge bevares for elementer med samme primære nøgle. Denne teknik bruges i databaser (ORDER BY col1, col2) og i radixsortering (hvert cifergennemløb skal være stabilt, for at den samlede algoritme er korrekt). Pythons sortering er altid stabil, så dette mønster fungerer pålideligt.
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)Hurtigt tjek
Afprøv din forståelse af begreberne fra lektionen Data Structures & Algorithms — Coding Interview Prep.
Opsummering af lektionen
I denne lektion lærte du: sammenligningsbaserede sorteringer har en nedre grænse på O(n log n) — at bryde denne grænse kræver ikke-sammenligningsbaseret information som heltal fra et begrænset område, tællesortering opnår O(n + k) ved at tælle frekvenser, radixsortering behandler cifre med O(d × (n + k)) i alt, og spandsortering udnytter ensartet fordeling til O(n) i gennemsnit, og Pythons Timsort er det praktiske standardvalg — stabil, O(n log n) i værste fald, O(n) i bedste fald og hurtigere end ethvert håndkodet alternativ på virkelige data. Næste gang behersker vi klassisk binær søgning.
Lær Python 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
- 30
- Lektioner
- 120
Ofte stillede spørgsmål
Er lektionen “Sortering uden sammenligning og Pythons sort()” gratis?
Ja — alle 3 lektioner i læringssporet DSA Interview Prep, inklusive “Sortering uden sammenligning og Pythons sort()”, kan læses gratis i deres fulde længde her på webstedet. Derefter låser CoddyKit PRO alle lektioner op samt interaktive øvelser med en indbygget kodeeditor og en AI-underviser døgnet rundt. DSA Interview Prep-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Sortering uden sammenligning og Pythons sort()”?
Udforsk counting sort og radix sort for heltalsarrays, og forstå, hvordan Pythons Timsort fungerer internt ved kald til den indbyggede sort. Du øver dig i DSA Interview Prep 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å DSA Interview Prep?
Der kræves ingen tidligere erfaring. DSA Interview Prep 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 4 af 4.
Hvor lang tid tager lektionen “Sortering uden sammenligning og Pythons sort()”?
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 DSA Interview Prep-lektion?
Ja. Alle DSA Interview Prep-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()