Sortowanie bez porównań: zliczanie, pozycyjne i kubełkowe

W części drugiej wszystkie algorytmy zatrzymały się w tym samym miejscu: O(n log n). To nie przypadek ani brak pomysłowości – to twierdzenie. Ale zaraz potem zobaczymy trzy algorytmy, które sortują szybciej. Sprzeczność jest pozorna i całe napięcie tego wpisu polega na tym, gdzie dokładnie ona znika.

Dlaczego n log n to granica

Wyobraź sobie algorytm, który wie o danych tylko tyle, ile powiedzą mu porównania: pyta „czy a jest mniejsze od b” i dostaje tak albo nie. Każdy taki algorytm da się narysować jako drzewo decyzyjne: w węzłach porównania, w gałęziach dwie możliwe odpowiedzi, w liściach gotowe uporządkowania.

Skoro na wejściu może być dowolna z n! permutacji, a algorytm musi każdą z nich rozróżnić, to drzewo musi mieć co najmniej n! liści. Drzewo binarne o wysokości h ma najwyżej 2^h liści, więc:

• 2^h ≥ n!
• h ≥ log₂(n!)
• ze wzoru Stirlinga: log₂(n!) ≈ n·log₂(n) − 1,44·n

Wysokość drzewa to liczba porównań w najgorszym przypadku. Zatem każdy algorytm oparty na porównaniach musi w pesymistycznym przypadku wykonać ich rzędu n log n. Nie da się tego obejść sprytniejszą implementacją – to ograniczenie informacyjne, nie inżynieryjne.

Ta granica jest zaskakująco ciasna. Dla n = 48 wychodzi log₂(48!) ≈ 202,9, czyli minimum 203 porównania. Sortowanie przez scalanie z naszego wyścigu wykonało ich 208 – jest o niecałe trzy procent od teoretycznego optimum. Dla miliona elementów minimum to około 18,5 miliona porównań i żadna biblioteka świata nie zejdzie niżej.

Sortowanie przez zliczanie

Counting sort jest tak prosty, że przez chwilę wygląda na oszustwo. Skoro wiesz, że wszystkie wartości to liczby całkowite z zakresu 0…k, to zamiast je porównywać, po prostu policz, ile razy każda występuje, a potem przepisz je z powrotem w kolejności rosnącej.

# Python
def counting_sort(data, k=None):
    """Zlicza wystąpienia wartości 0..k i przepisuje je w kolejności rosnącej."""
    if not data:
        return []
    if k is None:
        k = max(data)
    counts = [0] * (k + 1)
    for value in data:
        counts[value] += 1          # wartość użyta jako INDEKS – tu znika granica n log n
    result = []
    for value, times in enumerate(counts):
        result.extend([value] * times)
    return result

Zero porównań, O(n + k) czasu, O(k) pamięci. Licznik w animacji pokazuje twarde 0 w kolumnie porównań i to jest szczera prawda: ten kod ani razu nie sprawdza, czy jeden element jest większy od drugiego.

Haczyk siedzi w k. Dla wieku pracowników (0–120) czy ocen (1–6) to znakomity wybór. Dla 32-bitowych identyfikatorów k wynosi cztery miliardy i tablica liczników nie zmieści się w pamięci. Reguła jest prosta: sortowanie przez zliczanie ma sens, gdy k jest porównywalne z n.

Wersja wyżej gubi jednak coś ważnego – bo odtwarza elementy z samych liczników, więc działa tylko dla gołych liczb. Gdy sortujesz rekordy po kluczu (a nie same klucze), potrzebujesz wersji z sumami prefiksowymi, która jest przy okazji stabilna:

# Python
def counting_sort_stable(records, key, k):
    """Wersja dla rekordów: sumy prefiksowe dają pozycje docelowe, kolejność równych zachowana."""
    counts = [0] * (k + 1)
    for record in records:
        counts[key(record)] += 1
    for value in range(1, k + 1):
        counts[value] += counts[value - 1]        # sumy prefiksowe = pozycje końcowe
    result = [None] * len(records)
    for record in reversed(records):              # od tyłu, żeby zachować stabilność
        value = key(record)
        counts[value] -= 1
        result[counts[value]] = record
    return result

To właśnie ta wersja jest fundamentem następnego algorytmu.

Sortowanie pozycyjne

Radix sort rozwiązuje problem dużego k w sposób, który zna każdy, kto kiedyś sortował fiszki albo karty perforowane: nie sortuj po całej liczbie naraz, tylko cyfra po cyfrze. Najpierw po jednościach, potem po dziesiątkach, potem po setkach.

# Python
def radix_sort(data, base=10):
    """LSD: kolejne przebiegi po cyfrach, każdy STABILNYM sortowaniem przez zliczanie."""
    items = list(data)
    if not items:
        return items
    exp = 1
    biggest = max(items)
    while biggest // exp > 0:
        items = counting_by_digit(items, exp, base)
        exp *= base
    return items


def counting_by_digit(items, exp, base):
    """Jeden przebieg: rozdziel po cyfrze na pozycji exp, zachowując kolejność z poprzedniego."""
    counts = [0] * base
    for value in items:
        counts[(value // exp) % base] += 1
    for digit in range(1, base):
        counts[digit] += counts[digit - 1]
    result = [0] * len(items)
    for value in reversed(items):
        digit = (value // exp) % base
        counts[digit] -= 1
        result[counts[digit]] = value
    return result

Kluczowe jest jedno słowo: stabilnym. Przebieg po dziesiątkach ma prawo pomieszać elementy o tej samej cyfrze dziesiątek – gdyby to zrobił, zniszczyłby porządek ustalony w przebiegu po jednościach. Radix sort działa wyłącznie dlatego, że sortowanie każdej cyfry jest stabilne. To najlepszy praktyczny argument, że stabilność nie jest kaprysem teoretyków.

Złożoność to O(d·(n + k)), gdzie d to liczba cyfr, a k to podstawa. I tu warto być uczciwym: d zależy od zakresu danych, bo d = log_k(max). Radix sort nie unieważnia więc granicy n log n, tylko przesuwa koszt w miejsce, w którym zwykle jest tańszy – zamiast log n porównań na element mamy log_k(max) przebiegów po pamięci, a te są liniowe i przewidywalne. Przy 32-bitowych liczbach i podstawie 256 wychodzą cztery przebiegi, niezależnie od tego, czy sortujesz tysiąc, czy miliard rekordów.

Warianty, które warto znać:

• LSD (od najmniej znaczącej cyfry) – wersja z kodu wyżej. Prosta, stabilna, wymaga stałej długości klucza.
• MSD (od najbardziej znaczącej) – sortuje rekurencyjnie kubełki; naturalna dla napisów o różnej długości, bo krótkie napisy odpadają wcześniej.
• American flag sort – MSD wykonywany w miejscu, przez permutację cykliczną zamiast bufora. Nazwa pochodzi od trójkolorowego podziału tablicy; używany do sortowania napisów tam, gdzie liczy się pamięć.

W praktyce sortowanie pozycyjne bywa najszybszym sposobem uporządkowania dużych zbiorów liczb całkowitych o ograniczonej długości – identyfikatorów, znaczników czasu, kluczy w bazach kolumnowych. Da się nim sortować także liczby ujemne i zmiennoprzecinkowe, ale trzeba najpierw przekształcić ich reprezentację bitową tak, by porządek leksykograficzny bajtów odpowiadał porządkowi liczb (dla liczb zmiennoprzecinkowych IEEE 754 to odwrócenie bitu znaku i, dla ujemnych, całej reszty).

Sortowanie kubełkowe

Bucket sort zakłada coś innego niż dwa poprzednie: nie ograniczony zakres, tylko znany rozkład wartości. Dzielimy przedział na m kubełków, wrzucamy do nich elementy według wartości, sortujemy każdy kubełek osobno (zwykle przez wstawianie, bo są malutkie) i sklejamy wyniki po kolei.

# Python
from math import isqrt

def bucket_sort(data, buckets=None):
    """Rozrzuca elementy do kubełków wg wartości, sortuje każdy osobno i skleja."""
    items = list(data)
    if len(items) < 2:
        return items
    count = buckets or max(2, isqrt(len(items)))
    low, high = min(items), max(items)
    span = (high - low + 1) / count
    shelves = [[] for _ in range(count)]
    for value in items:
        index = min(count - 1, int((value - low) / span))
        shelves[index].append(value)
    result = []
    for shelf in shelves:
        result.extend(insertion_sort(shelf))      # kubełki są krótkie: wstawianie wygrywa
    return result

Jeśli dane są rozłożone równomiernie, każdy kubełek dostaje średnio n/m elementów i całość wychodzi liniowa. Jeśli nie są – wszystko ląduje w jednym kubełku i mamy z powrotem O(n²) sortowania przez wstawianie. Sortowanie kubełkowe jest więc jedynym algorytmem w tym cyklu, którego złożoność zależy nie od wielkości danych, tylko od tego, jak wyglądają.

W animacji widać zresztą jego mieszany charakter: licznik porównań nie stoi na zerze, bo w środku kubełków dzieje się zwykłe sortowanie porównawcze (w animacji wyżej, na 32 elementach, wychodzi ich 68). To hybryda, a nie czysty algorytm bez porównań.

Wyścig na danych, które im sprzyjają

Poniżej ta sama tablica dla wszystkich – tym razem 48 liczb z małego zakresu, czyli dokładnie taki materiał, do jakiego zaprojektowano te algorytmy. Quicksort dostaje ten sam zestaw dla porównania.

Liczby mówią same za siebie: sortowanie przez zliczanie – 0 porównań i 48 zapisów, pozycyjne – 0 porównań i 48 zapisów (przy jednocyfrowych wartościach wystarcza jeden przebieg), kubełkowe – 93 porównania wewnątrz kubełków. Quicksort na tych samych danych: 269 porównań i 234 zapisy, czyli praktycznie tyle samo, co na tablicy z losowymi wartościami. I to jest sedno: powtórzenia i wąski zakres nie pomagają algorytmowi porównawczemu w niczym, bo on o nich nie wie. Wygrana zliczania nie bierze się z lepszego kodu, tylko z wiedzy o danych.

Ciekawostka na marginesie: duplikaty potrafią algorytmowi porównawczemu wręcz zaszkodzić. Podział Lomuto z części drugiej na tablicy złożonej z samych identycznych wartości wykonuje maksymalnie nierówne podziały, czyli O(n²). Przy dziewięciu różnych wartościach na 48 elementów jeszcze tego nie widać, ale to właśnie dlatego prawdziwe biblioteki używają podziału trójdrożnego (mniejsze / równe / większe).

Kiedy naprawdę używać sortowań bez porównań

Podsumowanie z życia, nie z tabelki:

I najważniejsze zastrzeżenie: żaden z nich nie jest sortowaniem ogólnego przeznaczenia. Nie posortujesz nimi listy obiektów po dowolnym kluczu porównywalnym, nie użyjesz ich na napisach z polskimi znakami i regułami porównywania zależnymi od lokalizacji. Dlatego biblioteka standardowa żadnego popularnego języka nie ma ich jako domyślnego sort – dostajesz je co najwyżej w bibliotekach numerycznych i bazach danych, czyli tam, gdzie ktoś wie o danych więcej niż „da się je porównać”.

Ta wiedza jest tu trzecim zasobem, obok czasu i pamięci. Granica n log n dotyczy algorytmów, które nie wiedzą o danych nic. Jeśli wiesz cokolwiek – zakres, rozkład, długość klucza – możesz to zamienić na szybkość.

W ostatniej części schodzimy z teorii na ziemię: co dokładnie robi sorted() w Pythonie, Arrays.sort w Javie, std::sort w C++, sort() w PHP i JavaScripcie – i dlaczego w 2026 roku poprawna odpowiedź na pytanie „jakiego algorytmu używa Python” brzmi już inaczej niż pięć lat temu.