Algorytmy sortowania to fundament algorytmiki. Pojawiają się jako pytania własne („zaimplementuj merge sort"), jako wzorzec dziel-i-zwyciężaj („podziel i scal") oraz jako narzędzie wstępne („zacznij od posortowania"). Bez znajomości klas (stable, in-place, comparison) nie odpowiesz precyzyjnie na pytania o trade-offy.
Ten artykuł pokazuje sześć algorytmów + decyzję praktyczną na rozmowie: bubble, insertion, merge sort, quicksort, Timsort i wybór algorytmu. Każdy z trace step-by-step, sygnałami rozpoznawczymi i mechanizmami pułapek. Implementacje w Pythonie dla zwięzłości — algorytmy są language-agnostic (analogicznie w Java, C++, JavaScript, Ruby).
Pozostaję w obrębie comparison-based sortów + Timsorta. Counting sort, radix sort i bucket sort to non-comparison algorytmy, omawiam je tylko jako kontekst dla Ω(n log n) lower bound.
Algorytmy sortowania — definicja i klasy
Algorytm sortowania porządkuje kolekcję według klucza — wartości używanej do porównania. Kluczem może być liczba, napis, data albo wynik funkcji wyliczonej z rekordu (np. len(name) lub record.priority).
Intuicja: trzy wymiary klasyfikacji decydują o tym, który algorytm wybrać. Comparison-based używają relacji „mniejsze niż" i mają dolne ograniczenie Ω(n log n) w modelu porównań — kontekst klas złożoności: Big O w 10 minut. Stability decyduje czy kolejność równych kluczy jest zachowana. In-place vs out-of-place decyduje o pamięci pomocniczej.
Comparison-based Stable In-place Best Avg Worst
─────────────────────────────────────────────────────────────
Bubble sort Yes Yes O(n) O(n²) O(n²)
Insertion sort Yes Yes O(n) O(n²) O(n²)
Merge sort Yes No* O(nlogn) O(nlogn) O(nlogn)
Quicksort No Yes O(nlogn) O(nlogn) O(n²)
Timsort Yes No* O(n) O(nlogn) O(nlogn)
* O(n) extra space dla scalania
records = [("Ada", "math", 2), ("Ben", "math", 1), ("Ewa", "algo", 3)]
by_subject = sorted(records, key=lambda record: record[1])
print(by_subject)
# expected_output: [('Ewa', 'algo', 3), ('Ada', 'math', 2), ('Ben', 'math', 1)]
Pułapka: stabilność NIE oznacza usuwania duplikatów. Mechanizm błędu: kandydat mówi „stable sort usuwa duplikaty" — ale stable oznacza tylko że elementy z tym samym kluczem nie zamieniają się miejscami względem pierwotnej kolejności. Wszystkie duplikaty pozostają w wyniku.
Bubble sort — prosty wzorzec zamian
Bubble sort wielokrotnie przechodzi po tablicy, porównuje sąsiednie elementy i zamienia je miejscami gdy są w złej kolejności. Po jednej pełnej iteracji największy element trafia na koniec.
Intuicja: największa liczba „przebąbluje" do końca tablicy w pierwszym przejściu, druga największa w drugim przejściu, i tak dalej. Złożoność średnia i pesymistyczna to O(n²) — wykonuje wiele lokalnych porównań. Wariant z flagą swapped może zakończyć się po jednym przejściu dla danych już posortowanych (O(n) best case).
Na rozmowie bubble sort pojawia się głównie jako wzorzec edukacyjny do pokazania lokalnego swap pattern. W produkcyjnym kodzie prawie zawsze przegrywa z sorted() (Timsort) lub nawet insertion_sort().
def bubble_sort(values):
result = values[:]
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8])) # expected_output: [1, 2, 4, 5, 8]
Pułapka: bubble sort i insertion sort mają oba O(n²), ale NIE są praktycznie równoważne. Mechanizm błędu: kandydat zakłada że obie klasy O(n²) są wymienne — ale bubble wykonuje więcej zamian (każda parzysta para się zamienia), insertion robi przesunięcia (jedna pamięć tymczasowa). Bubble jest narzędziem dydaktycznym; insertion ma realne zastosowanie dla nearly-sorted.
Insertion sort — dobry dla nearly sorted
Insertion sort buduje posortowany prefiks listy. Każdy kolejny element jest przesuwany w lewo aż znajdzie miejsce przed większymi elementami i po mniejszych lub równych. To jak sortowanie kart w ręce.
Intuicja: dla danych prawie posortowanych większość elementów jest już na właściwych pozycjach, więc liczba przesunięć jest mała — best case O(n). Średnio O(n²), ale stałe są małe — często szybszy niż merge sort dla n < 50. Z tego powodu Timsort używa insertion sort dla małych podproblemów.
Stabilność insertion sort zależy od warunku przesuwania: > zachowuje kolejność równych kluczy (stable), >= ją niszczy (unstable). To subtelny detal, ale często testowany na rozmowie.
def insertion_sort(values):
result = values[:]
for index in range(1, len(result)):
current = result[index]
position = index - 1
while position >= 0 and result[position] > current:
result[position + 1] = result[position]
position -= 1
result[position + 1] = current
return result
print(insertion_sort([1, 2, 4, 3, 5])) # expected_output: [1, 2, 3, 4, 5]
Pułapka: stabilność insertion sort zależy od warunku > vs >=. Mechanizm błędu: kandydat pisze result[position] >= current w warunku przesuwania — algorytm przesuwa elementy z równym kluczem przed siebie, niszcząc oryginalną kolejność. Naprawa: użyj ścisłego >, żeby równe klucze zostawały na miejscu.
Merge sort — dziel, sortuj i scalaj
Merge sort dzieli wejście na połowy, rekurencyjnie sortuje części, a potem scala dwie posortowane sekwencje. To klasyczny dziel-i-zwyciężaj — trudność leży w poprawnym merge, nie w podziale.
Intuicja: drzewo wywołań rekurencyjnych ma głębokość log₂(n) (każdy poziom dzieli problem na pół). Każde piętro scalenia dotyka łącznie n elementów, więc całkowity koszt to n × log n = O(n log n) gwarantowane, także w worst case. Ten sam wzorzec halve-the-space występuje w wyszukiwaniu binarnym.
Standardowy merge sort jest stabilny gdy przy równych kluczach wybiera element z lewej części. Kosztem przewidywalności jest O(n) extra space na scalane fragmenty.
def merge_sort(values):
if len(values) <= 1:
return values[:]
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
merged, left_index, right_index = [], 0, 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
merged.append(left[left_index])
left_index += 1
else:
merged.append(right[right_index])
right_index += 1
merged.extend(left[left_index:])
merged.extend(right[right_index:])
return merged
print(merge_sort([6, 3, 8, 1, 3])) # expected_output: [1, 3, 3, 6, 8]
Trace dla merge_sort([6, 3, 8, 1, 3]):
Krok 1: dziel na [6, 3] i [8, 1, 3].
Krok 2: rekurencja → merge_sort([6, 3]) zwraca [3, 6], merge_sort([8, 1, 3]) zwraca [1, 3, 8].
Krok 3: scalanie [3, 6] z [1, 3, 8]. Porównaj 3 vs 1 → bierz 1. 3 vs 3 → bierz lewy 3 (stable!). 6 vs 3 → bierz prawy 3. Itd.
Krok 4: wynik [1, 3, 3, 6, 8].
Klucz: rekurencja dzieli (top-down), scalanie buduje wynik (bottom-up). Stabilność wynika z <= (lewy pierwszy przy równości).
Pułapka: merge sort jest stabilny w klasycznej implementacji, quicksort zwykle NIE. Mechanizm błędu: kandydat zakłada że oba algorytmy dziel-i-zwyciężaj mają tę samą charakterystykę — ale sama etykieta nic nie mówi o stabilności ani pamięci. Naprawa: pamiętaj merge sort = stable + O(n) space, quicksort = unstable + O(log n) space typically.
Quicksort — partycjonowanie wokół pivota
Quicksort wybiera pivot, partycjonuje dane na elementy mniejsze i większe, sortuje części rekurencyjnie. Dobrze dobrany pivot daje małe podproblemy i średni czas O(n log n).
Intuicja: zamiast dzielić na pół (jak merge sort), quicksort dzieli wokół wartości — wszystko mniejsze idzie w lewo, większe w prawo, równe zostaje. Jeśli pivot jest blisko mediany, partycje są ~równe i głębokość rekurencji to log n. Jeśli pivot jest minimum lub maximum, jedna partycja ma n-1 elementów — degeneruje do O(n²).
Pesymistyczne O(n²) pojawia się przy złym pivocie — np. zawsze pierwszy element dla danych już posortowanych. Randomizacja pivota zmniejsza ryzyko deterministycznego worst case, ale nie eliminuje go matematycznie. Quicksort może być in-place (partycjonowanie tej samej tablicy z dwoma wskaźnikami), ale typowe implementacje NIE są stabilne.
from random import Random
def quicksort(values, random):
if len(values) <= 1:
return values[:]
pivot = random.choice(values)
smaller = [v for v in values if v < pivot]
equal = [v for v in values if v == pivot]
larger = [v for v in values if v > pivot]
return quicksort(smaller, random) + equal + quicksort(larger, random)
rng = Random(7)
print(quicksort([4, 1, 3, 2, 4], rng)) # expected_output: [1, 2, 3, 4, 4]
Pułapka: randomizowany pivot NIE usuwa matematycznie pesymistycznego O(n²). Mechanizm błędu: kandydat mówi „randomizacja gwarantuje O(n log n)" — ale teoretycznie zły układ wejścia + niefortunna sekwencja losowych wyborów wciąż może dać O(n²). W praktyce prawdopodobieństwo jest astronomicznie małe, ale matematyczna gwarancja pozostaje O(n²). Naprawa: mów „randomizacja zmniejsza ryzyko deterministycznego worst case", nie „eliminuje".
Timsort — adaptive merge+insertion (Python default)
Timsort łączy idee merge sort i insertion sort. Wykrywa naturalne runy (już uporządkowane fragmenty), rozszerza małe runy techniką podobną do insertion sort, a potem stabilnie scala merge sortem.
Intuicja: realne dane często mają fragmenty już posortowane (np. timestamps rosnące, listy z paroma niewłaściwie wstawionymi elementami). Standardowy merge sort tego nie wykorzysta — Timsort tak. Best case O(n) dla danych już posortowanych, average i worst O(n log n). Stable z definicji (wewnętrzny merge wybiera lewy przy równych kluczach).
W Pythonie sorted() zwraca nową listę, list.sort() modyfikuje listę w miejscu i zwraca None. To dwa interfejsy operacji, nie różne algorytmy — oba używają Timsort pod spodem.
numbers = [3, 1, 2]
new_numbers = sorted(numbers)
print(new_numbers) # expected_output: [1, 2, 3]
print(numbers) # expected_output: [3, 1, 2]
result = numbers.sort()
print(result) # expected_output: None
print(numbers) # expected_output: [1, 2, 3]
Pułapka: domyślne sortowanie zależy od runtime języka. Mechanizm błędu: kandydat mówi „domyślny sort jest stable" sugerując uniwersalność — ale Python używa Timsort (stable), Java tak (Collections.sort), a wiele innych środowisk (C++ STL std::sort, V8) wybiera introsort (unstable). Naprawa: nie przenoś założeń o stabilności między językami bez sprawdzenia dokumentacji.
Wybór algorytmu sortowania na rozmowie
Bubble sort wybieraj tylko jako przykład edukacyjny. W produkcyjnym kodzie prawie zawsze przegrywa — biblioteka standardowa (Timsort/introsort) jest szybsza i stabilna.
Insertion sort ma sens dla małych lub prawie posortowanych danych. Merge sort gdy ważne są stabilność i gwarantowany czas O(n log n). Quicksort gdy liczy się mała pamięć (O(log n) stack vs O(n) merge buffer) i dobry średni przypadek. Timsort gdy chcesz najlepszego z obu światów na realnych danych.
Dla zwykłego kodu aplikacyjnego najlepsza odpowiedź na rozmowie to użycie domyślnego sortowania biblioteki. W Pythonie sorted() dla nowej listy, list.sort() dla modyfikacji istniejącej. Pisanie własnego merge sort od zera jest sensowne tylko gdy rozmówca wprost prosi o implementację.
items = [
{"name": "Ada", "group": "B", "score": 10},
{"name": "Ben", "group": "A", "score": 10},
{"name": "Ewa", "group": "B", "score": 8},
]
by_score_then_group = sorted(items, key=lambda item: item["score"])
by_score_then_group = sorted(by_score_then_group, key=lambda item: item["group"])
print([item["name"] for item in by_score_then_group])
# expected_output: ['Ben', 'Ewa', 'Ada']
Pułapka: przy multi-key sort stabilność jest mechanizmem, nie estetyką. Mechanizm błędu: kandydat sortuje po obu kluczach jednocześnie z key=lambda x: (x.score, x.group) — działa, ale jeśli rozmówca chce demonstracji wielu osobnych sortowań, bez stable każdy kolejny sort niszczy wynik poprzedniego. Naprawa: zacznij od pomocniczego klucza, kończ na głównym — wykorzystuje stabilność do warstwowania kryteriów.
Sygnały rozpoznawcze zadań na sortowanie
Zadanie pachnie sortowaniem gdy widzisz monotoniczność, porządek lub potrzebę porównania par. Sygnał → algorytm:
"sorted output / kth smallest" → sorted() lub heap
"stable sort / preserve order" → merge sort lub Timsort
"in-place + tight memory" → quicksort (in-place wariant)
"nearly sorted data" → insertion sort lub Timsort
"only small subset matters / top K" → heap (heapq), nie pełny sort
"counting / fixed range integers" → counting sort, radix sort
"multi-key sort" → Timsort z kluczem złożonym
"sort jako preprocessing" → sorted() przed bisect/two-pointers
Sygnały odwrotne — kiedy sortowanie NIE pasuje: lookup po dokładnym kluczu (→ hash mapa O(1)), dynamiczny insert/delete z porządkiem (→ BST O(log n)), strumień danych bez końca (→ heap top-K).
patterns = {
"stable multi-key sort": "Timsort (Python sorted)",
"in-place + small memory": "quicksort",
"nearly sorted data": "insertion sort or Timsort",
}
print(patterns["stable multi-key sort"]) # expected_output: Timsort (Python sorted)
Kiedy NIE sortować
Sortowanie nie jest darmowe — koszt O(n log n) jest często marnotrawstwem gdy nie potrzebujesz pełnego porządku. Konkretny anty-przykład: zadanie „znajdź najmniejszy element" — pełen sort to O(n log n), podczas gdy min() to O(n). Różnica nieistotna dla n=100, dramatyczna dla n=10⁶.
Drugi anty-przykład: „znajdź czy element istnieje w kolekcji". Sortowanie + binary search = O(n log n + log n) setup. Hash set = O(n) setup + O(1) lookup. Hash wygrywa dla single lookup; sortowanie + bisect wygrywa gdy planujesz wiele wyszukiwań.
Trzeci anty-przykład: „top K elementów" dla K << n. Pełen sort to O(n log n), heap-based top-K to O(n log K) — dla K=10 w kolekcji n=10⁶ różnica to ~7 mln vs ~33 mln operacji.
import heapq
values = [5, 2, 8, 1, 9, 3]
print(min(values)) # expected_output: 1
seen = set(values)
print(8 in seen) # expected_output: True
print(heapq.nsmallest(2, values)) # expected_output: [1, 2]
Najczęstsze błędy
list.sort() zwraca None, nie listę. Klasyczny błąd: result = numbers.sort() — result jest None, bo sort() modyfikuje listę in-place. Naprawa: result = sorted(numbers) (nowa lista) albo numbers.sort(); result = numbers (in-place).
Założenie że quicksort jest stabilny. Typowe implementacje quicksort są unstable — partycjonowanie z dwoma wskaźnikami zamienia elementy o równych kluczach. Mechanizm błędu: kandydat używa quicksort do multi-key sort, drugi sort niszczy pierwszy. Naprawa: do multi-key zawsze używaj stable (merge sort, Timsort).
Merge sort O(n log n) ALE O(n) extra space. Łatwo zapomnieć o pamięci. Dla bardzo dużych danych quicksort in-place może być lepszy mimo O(n²) worst case (rzadkiego przy randomizacji). Naprawa: zawsze podawaj parę (czas, pamięć) zamiast samego czasu.
Comparison-based ma Ω(n log n). To dolne ograniczenie matematyczne — żaden comparison sort nie może być asymptotycznie szybszy. Counting sort i radix sort obchodzą to przez niewiększość porównań (operują na cyfrach/wartościach), ale działają tylko dla specjalnych typów danych (małe liczby całkowite).
Bubble sort jako „dobry pierwszy algorytm". Edukacyjnie OK, ale na rozmowie nie pisz bubble sort jeśli pytanie nie jest wprost o niego. Insertion sort jest tak samo prosty i ma realne zastosowanie. Mechanizm błędu: kandydat traci punkty za pokazanie najsłabszego algorytmu O(n²).
FAQ
Czy Python ma w bibliotece quicksort albo merge sort?
Nie wprost. sorted() i list.sort() używają Timsort (stable, adaptive). Jeśli wprost chcesz quicksort lub merge sort, musisz napisać sam — nie ma osobnego API w stdlib. To celowa decyzja: Timsort dominuje praktycznie nad oboma w realnych przypadkach. Inne biblioteki (NumPy np.sort) mają parametr kind='quicksort'/'mergesort'/'heapsort' dla niestandardowych potrzeb.
Co używa Java, JavaScript, C++?
Java Collections.sort używa Timsort (stable). JavaScript V8 historycznie używał quicksort, od 2018 (V8 7.0) używa Timsort. C++ STL std::sort używa introsort (hybryda quicksort + heap sort + insertion sort dla małych podproblemów) — unstable, ale std::stable_sort istnieje jako osobna funkcja. Nie przenoś założeń o stabilności między językami bez sprawdzenia.
Czy quicksort jest szybszy od merge sort w praktyce?
Często tak, mimo że oba mają O(n log n) average. Powody: quicksort ma mniejsze stałe (proste partycjonowanie vs alokacja merge buffer), lepsze cache locality (operuje na ciągłej pamięci), O(log n) extra space dla call stack vs O(n) dla merge. Dla dużych danych z dobrym pivotem quicksort wygrywa. Merge sort wybierasz gdy potrzebujesz stabilności lub gwarantowanego O(n log n) worst case.
Co to introsort?
Hybryda quicksort + heap sort. Zaczyna jako quicksort, ale jeśli głębokość rekurencji przekracza 2*log(n) (sygnał złego pivota), przechodzi na heap sort, który ma O(n log n) worst case. Najlepsze z obu: szybkość quicksortu w średnim przypadku + gwarancja O(n log n) w worst case. Używany w C++ STL i (historycznie) V8.
Kiedy używać sort() zamiast sorted()?
list.sort() gdy nie potrzebujesz oryginalnej kolekcji — modyfikuje in-place, oszczędza O(n) pamięci. sorted() gdy chcesz zostawić oryginał albo sortujesz coś innego niż lista (sorted(set), sorted(dict.items())). Wydajność niemal identyczna; różnica głównie semantyczna. W kodzie funkcyjnym preferuj sorted() (no side effects).
Jak sortować po wielu kluczach jednocześnie?
Najczystsze: sorted(items, key=lambda x: (x.priority, x.name)) — Python porównuje tuple element po elemencie. Dla descending na jednym kluczu: key=lambda x: (-x.priority, x.name) (negacja). Alternatywa: dwa osobne sorted() od najmniej do najważniejszego klucza (wykorzystuje stabilność Timsort). Pierwsza opcja czytelniejsza dla 2-3 kluczy, druga elastyczniejsza dla dynamicznych kluczy.
Powiązane tematy
- Big O w 10 Minut — Notacja Złożoności — kontekst dla
O(n log n)jako klasy wzrostu i porównanie zO(n²),O(log n). - Wyszukiwanie Binarne — Dziel-i-Zwyciężaj — sortowanie jest kosztem setup'u przed binary search; ten artykuł rozwija wzorzec halve-the-space.
- Drzewa Binarne — Wzorzec Rekurencyjny — BST jako alternatywa dla sortowania + binsearch gdy potrzebujesz dynamicznego utrzymania porządku.
Sprawdź swoją wiedzę quizem
Przerób ten artykuł w 15-pytaniowy quiz testujący stabilność, in-place, comparison vs counting, klasy złożoności i wybór algorytmu: https://odpytywarka.pl/q/PWXZMp.
Masz własne notatki na rozmowę? Wgraj PDF lub wklej tekst na stworz-quiz-z-pdf — pierwsze 3 strony PDF i 15 pytań jednokrotnego wyboru za darmo, generowanie 30-60 sekund.
Źródła
- Sorting algorithm — Wikipedia — klasy, comparison-based, stable
- Merge sort — Wikipedia
- Quicksort — Wikipedia
- Timsort — Wikipedia — Python default
- Python
sorted()ilist.sort()