Sortowania nieporównawcze i sort() w Pythonie
Poznają Państwo sortowanie przez zliczanie i sortowanie pozycyjne dla tablic liczb całkowitych oraz zrozumieją działanie algorytmu Timsort używanego wewnętrznie przez wbudowane wywołania sort.
Sortowania nieporównawcze i sort() w Pythonie to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Dolne ograniczenie O(n log n) dla porównań
Każdy algorytm sortowania, który ustala kolejność wyłącznie na podstawie porównań elementów, wymaga w najgorszym przypadku co najmniej Ω(n log n) porównań. Dowodzi się tego za pomocą argumentu drzewa decyzyjnego: posortowanie n elementów wymaga rozróżnienia n! możliwych uporządkowań. Binarne drzewo decyzyjne (każdy jego węzeł jest porównaniem) potrzebuje co najmniej log₂(n!) ≈ n log₂(n) poziomów. Aby przekroczyć tę granicę, potrzebujemy dodatkowych informacji o elementach — na przykład wiedzy, że są to ograniczone liczby całkowite.
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 sortingSortowanie przez zliczanie: sortowanie według częstości
Sortowanie przez zliczanie polega na zliczeniu częstości występowania każdej wartości, a następnie odtworzeniu posortowanej tablicy na podstawie tych zliczeń. Wymaga wcześniejszej znajomości zakresu wartości [0, k). Złożoność czasowa: O(n + k); złożoność pamięciowa: O(k). Dla małego k w porównaniu z n (np. przy sortowaniu wieku z zakresu 0–120 lub pojedynczych cyfr) sortowanie przez zliczanie jest szybsze od wszystkich sortowań opartych na porównaniach. Dla dużego k koszt O(k) pamięci sprawia, że staje się ono niepraktyczne.
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)Stabilne sortowanie przez zliczanie z użyciem skumulowanych zliczeń
W przypadku stabilnego sortowania przez zliczanie (co jest istotne podczas sortowania obiektów według klucza) należy obliczyć skumulowane zliczenia, tak aby cum[v] wskazywało pozycję początkową wartości v w tablicy wynikowej. Należy przetwarzać tablicę wejściową od prawej do lewej, umieszczając każdy element na pozycji cum[key] - 1 i zmniejszając tę wartość. W ten sposób powstaje stabilnie posortowana tablica — elementy o tym samym kluczu zachowują pierwotną kolejność względem siebie.
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]Sortowanie pozycyjne: sortowanie cyfra po cyfrze
Sortowanie pozycyjne sortuje liczby całkowite cyfra po cyfrze, od najmniej znaczącej cyfry (LSD) do najbardziej znaczącej (MSD), używając stabilnego sortowania (takiego jak sortowanie przez zliczanie) na każdej pozycji cyfry. Po d przebiegach (po jednym dla każdej cyfry) tablica jest w pełni posortowana. Złożoność czasowa wynosi O(d × (n + k)), gdzie d = liczba cyfr, a k = podstawa systemu (zwykle 10). Dla n liczb całkowitych ograniczonych przez W mamy d = log_k(W), co daje łącznie 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]Sortowanie kubełkowe: rozdzielanie do kubełków
Sortowanie kubełkowe rozdziela elementy do ustalonej liczby kubełków na podstawie zakresu wartości, sortuje każdy kubełek (używając sortowania przez wstawianie dla małych kubełków), a następnie je łączy. Dla równomiernie rozłożonych danych w przedziale [0, 1), n kubełków zapewnia średnią złożoność czasową O(n). Złożoność czasowa wynosi średnio O(n + k), a w najgorszym przypadku O(n²) (gdy wszystkie elementy trafią do jednego kubełka). Sortowanie to jest najbardziej użyteczne, gdy rozkład danych jest znany i w przybliżeniu równomierny.
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 w Pythonie od podszewki
Funkcje sorted() i list.sort() w Pythonie używają algorytmu Timsort, zaprojektowanego przez Tima Petersa w 2002 roku. Timsort jest hybrydą sortowania przez scalanie i sortowania przez wstawianie. Wyszukuje „naturalne serie” (podsekwencje, które są już posortowane) i używa sortowania przez wstawianie do tworzenia serii o długości do 64 elementów. Następnie scala serie za pomocą sortowania przez scalanie, stosując kilka optymalizacji: galloping (pomijanie całych partii elementów, gdy jedna seria wyraźnie dominuje) oraz układanie serii na stosie według ich długości.
# 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')Python: sort() a sorted() — najważniejsze różnice
list.sort() sortuje listę w miejscu, zwraca None i działa wyłącznie na listach. sorted(iterable) działa na dowolnym obiekcie iterowalnym (krotkach, generatorach, słownikach) i zwraca nową listę. Obie funkcje przyjmują parametry key i reverse. Częsty błąd polega na przypisaniu wyniku lst.sort() do zmiennej, a następnie zastanawianiu się, dlaczego jej wartość to None. Należy używać sorted(), gdy potrzebują Państwo posortowanej wersji i chcą zachować oryginał.
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)Niestandardowe klucze sortowania na rozmowach rekrutacyjnych
Sortowanie w Pythonie przyjmuje funkcję key, która jest obliczana raz dla każdego elementu (w przeciwieństwie do komparatora w języku C, wywoływanego dla każdej pary). Często używane klucze sortowania na rozmowach rekrutacyjnych to: len dla długości ciągu znaków, lambda x: -x dla sortowania malejącego, lambda x: (x[1], x[0]) dla sortowania według wielu kluczy oraz str.lower dla sortowania bez uwzględniania wielkości liter. Sortowanie w Pythonie jest gwarantowanie stabilne, dlatego sortowanie według wielu kluczy działa poprawnie.
# 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]Kiedy używać poszczególnych algorytmów sortowania na rozmowach rekrutacyjnych
Należy wybrać właściwy algorytm sortowania w zależności od kontekstu:
- Użycie sorted()/list.sort() w Pythonie: domyślny wybór w zadaniach rekrutacyjnych — Timsort jest optymalny
- Sortowanie przez zliczanie: gdy wartości są małymi, ograniczonymi liczbami całkowitymi (od 0 do k, przy małym k)
- Sortowanie pozycyjne: gdy sortowanych jest wiele liczb całkowitych o znanej szerokości bitowej lub liczbie cyfr
- Sortowanie kubełkowe: gdy dane to równomiernie rozłożone liczby zmiennoprzecinkowe z określonego zakresu
- Implementacja sortowania przez scalanie: gdy wymagane jest samodzielne napisanie stabilnego sortowania o złożoności O(n log n)
# 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]Sortowanie bez sortowania: elementy top-k z użyciem kopca
Wiele zadań rekrutacyjnych wymaga uzyskania wyników podobnych do sortowania bez konieczności pełnego sortowania. Znalezienie k największych elementów za pomocą kopca minimum o rozmiarze k zajmuje O(n log k) — czyli mniej niż O(n log n), gdy k << n. Znalezienie k-tego największego elementu za pomocą algorytmu quickselect zajmuje średnio O(n). Znalezienie mediany z użyciem podejścia z dwoma kopcami zajmuje O(log n) na każde wstawienie. Warto znać te podejścia do częściowego sortowania jako szybsze alternatywy dla pełnego sortowania.
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)) # 5Stabilność sortowania przy sortowaniu według wielu kluczy
Stabilność umożliwia poprawne sortowanie według wielu kluczy: najpierw należy stabilnie sortować według klucza drugorzędnego, a następnie stabilnie według klucza głównego. Kolejność według klucza drugorzędnego zostaje zachowana dla elementów o takich samych wartościach klucza głównego. Technika ta jest używana w bazach danych (ORDER BY col1, col2) oraz w sortowaniu pozycyjnym (każdy przebieg dla kolejnej cyfry musi być stabilny, aby cały algorytm działał poprawnie). Sortowanie w Pythonie jest zawsze stabilne, więc ten schemat działa niezawodnie.
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)Szybkie sprawdzenie
Sprawdź swoją wiedzę na temat zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyli się Państwo, że: sortowania oparte na porównaniach mają dolne ograniczenie O(n log n) — jego przekroczenie wymaga informacji niezwiązanych z porównywaniem, takich jak ograniczony zakres liczb całkowitych, sortowanie przez zliczanie osiąga O(n + k), zliczając częstości, sortowanie pozycyjne przetwarza cyfry i zajmuje łącznie O(d × (n + k)), a sortowanie kubełkowe wykorzystuje równomierny rozkład danych, osiągając średnio O(n), oraz że Timsort w Pythonie jest praktycznym wyborem domyślnym — jest stabilny, ma złożoność O(n log n) w najgorszym przypadku i O(n) w najlepszym, a dla rzeczywistych danych jest szybszy niż każda alternatywa napisana ręcznie. Następnie opanujemy klasyczne wyszukiwanie binarne.
Często zadawane pytania
Czy lekcja „Sortowania nieporównawcze i sort() w Pythonie” jest bezpłatna?
Tak — pełny tekst „Sortowania nieporównawcze i sort() w Pythonie” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowania nieporównawcze i sort() w Pythonie”?
Poznają Państwo sortowanie przez zliczanie i sortowanie pozycyjne dla tablic liczb całkowitych oraz zrozumieją działanie algorytmu Timsort używanego wewnętrznie przez wbudowane wywołania sort. Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Sortowania nieporównawcze i sort() w Pythonie”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie bąbelkowe i przez wstawianie
- Sortowanie przez scalanie: podziel, posortuj, scal
- Quick Sort i wybór pivota
- Sortowania nieporównawcze i sort() w Pythonie