Icke-jämförande sorteringar och Pythons sort()
Utforska counting sort och radix sort för heltalsarrayer och förstå hur Pythons Timsort fungerar bakom kulisserna vid anrop av den inbyggda sort-funktionen.
Icke-jämförande sorteringar och Pythons sort() är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Den undre gränsen O(n log n) för jämförelser
Varje sorteringsalgoritm som bestämmer ordningen endast genom jämförelser av element kräver minst Ω(n log n) jämförelser i värsta fall. Detta bevisas med beslutsträdsargumentet: för att sortera n element måste man skilja mellan n! möjliga ordningar. Ett binärt beslutsträd (där varje nod är en jämförelse) behöver minst log₂(n!) ≈ n log₂(n) nivåer. För att komma runt denna gräns behöver vi ytterligare information om elementen – till exempel att de är begränsade heltal.
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: sortera efter frekvens
Counting sort fungerar genom att räkna frekvensen för varje värde och sedan återskapa den sorterade arrayen utifrån antalen. Det kräver att värdeintervallet [0, k) är känt i förväg. Tidskomplexiteten är O(n + k) och komplexiteten för utrymme är O(k). För små k i förhållande till n (t.ex. sortering av åldrarna 0–120 eller ensiffriga tal) är counting sort snabbare än alla jämförelsebaserade sorteringar. För stora k gör kostnaden O(k) för utrymme algoritmen opraktisk.
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 kumulativa frekvenser
För en stabil counting sort (viktigt när objekt sorteras efter en nyckel) beräknar du kumulativa frekvenser så att cum[v] anger startpositionen för värdet v i resultatet. Gå igenom indatarrayen från höger till vänster, placera varje element på positionen cum[key] - 1 och minska den positionen. Då blir sorteringen stabil – element med samma nyckel behåller sin inbördes ursprungliga ordning.
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: sortera siffra för siffra
Radixsortering sorterar heltal siffra för siffra, från den minst signifikanta siffran (LSD) till den mest signifikanta (MSD), med hjälp av en stabil sortering (till exempel counting sort) vid varje sifferposition. Efter d genomkörningar (en per siffra) är arrayen helt sorterad. Tidskomplexitet: O(d × (n + k)) där d = antal siffror och k = basen (vanligtvis 10). För n heltal begränsade av W är d = log_k(W), vilket ger totalt 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: fördela i hinkar
Bucket sort fördelar element i ett fast antal hinkar baserat på värdeintervall, sorterar varje hink (med insertion sort för små hinkar) och sammanfogar dem. För jämnt fördelade data i [0, 1) ger n hinkar en genomsnittlig tidskomplexitet på O(n). Tid: O(n + k) i genomsnitt och O(n²) i värsta fall (alla element hamnar i samma hink). Mest användbar när datans fördelning är känd och ungefär jämn.
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 huven
Pythons sorted() och list.sort() använder Timsort, som designades av Tim Peters 2002. Timsort är en hybrid av merge sort och insertion sort. Den söker efter ”naturliga körningar” (delsekvenser som redan är sorterade) och använder insertion sort för att bygga körningar på upp till 64 element. Därefter sammanfogar den körningarna med merge sort och flera optimeringar: galloping (hoppar över element i större block när en körning dominerar) och stackning av körningslängder.
# 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(): viktiga skillnader
list.sort() sorterar på plats, returnerar None och fungerar bara med listor. sorted(iterable) fungerar med alla itererbara objekt (tupler, generatorer och dictionaries) och returnerar en ny lista. Båda tar emot parametrarna key och reverse. Ett vanligt fel är att tilldela returvärdet från lst.sort() till en variabel och sedan undra varför det är None. Använd alltid sorted() när du behöver den sorterade versionen och vill behålla originalet.
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)Anpassade sorteringsnycklar i intervjuer
Pythons sortering accepterar en key-funktion som utvärderas en gång per element (till skillnad från C:s komparator, som anropas för varje par). Vanliga sorteringsnycklar i intervjuer är len för stränglängd, lambda x: -x för fallande ordning, lambda x: (x[1], x[0]) för sortering med flera nycklar och str.lower för skiftlägesokänslig sortering. Pythons sortering är garanterat stabil, så sortering med flera nycklar fungerar 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 ska du använda de olika sorteringsalgoritmerna i intervjuer
Välj rätt sorteringsalgoritm utifrån sammanhanget:
- Använd Python's sorted()/list.sort(): standardvalet för alla intervjuproblem – Timsort är optimalt
- Counting sort: när värdena är små, begränsade heltal (0 till k, där k är litet)
- Radix sort: när du sorterar många heltal med känd bitbredd eller känt antal siffror
- Bucket sort: när data består av jämnt fördelade flyttal inom ett känt intervall
- Implementera merge sort: när du ombeds skriva en stabil sortering med O(n log n) från grunden
# 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]Sortera utan sortering: topp-k med en heap
Många intervjuproblem efterfrågar resultat som liknar sortering utan att kräva en fullständig sortering. För att hitta de k största elementen körs en min-heap med storleken k på O(n log k) – snabbare än O(n log n) när k << n. För att hitta det k:te största elementet har quickselect den genomsnittliga komplexiteten O(n). För att hitta medianen har metoden med två heapar komplexiteten O(log n) per insättning. Dessa metoder för delvis sortering är värda att känna till som snabbare alternativ till fullständig 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 vid sortering med flera nycklar
Stabilitet möjliggör korrekt sortering med flera nycklar: sortera först efter sekundärnyckeln (stabilt) och sedan efter primärnyckeln (stabilt). Sekundärordningen bevaras när primärnyckeln är lika. Denna teknik används i databaser (ORDER BY col1, col2) och i radix sort (varje sifferpass måste vara stabilt för att algoritmen som helhet ska bli korrekt). Pythons sortering är alltid stabil, så detta mönster fungerar tillförlitligt.
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)Snabbtest
Testa dina kunskaper om begreppen i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde du dig: jämförelsebaserade sorteringar har en undre gräns på O(n log n) – för att överskrida denna gräns krävs information som inte bygger på jämförelser, till exempel begränsade heltal, counting sort uppnår O(n + k) genom att räkna frekvenser, radix sort behandlar siffror med totalt O(d × (n + k)) och bucket sort utnyttjar en jämn fördelning för O(n) i genomsnitt, samt Pythons Timsort är det praktiska standardvalet – stabilt, O(n log n) i värsta fall, O(n) i bästa fall och snabbare än alla handskrivna alternativ för verkliga data. Nästa steg är att bemästra klassisk binärsökning.
Lär dig Förberedelse inför kodningsintervjuer med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Icke-jämförande sorteringar och Pythons sort()” gratis?
Ja – hela texten till ”Icke-jämförande sorteringar och Pythons sort()” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Icke-jämförande sorteringar och Pythons sort()”?
Utforska counting sort och radix sort för heltalsarrayer och förstå hur Pythons Timsort fungerar bakom kulisserna vid anrop av den inbyggda sort-funktionen. Ni övar på Förberedelse inför kodningsintervjuer med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 4 av 4.
Hur lång tid tar lektionen ”Icke-jämförande sorteringar och Pythons sort()”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Bubble sort och insertion sort
- Merge sort: dela, sortera, sammanfoga
- Quick sort och pivotval
- Icke-jämförande sorteringar och Pythons sort()