Algorytmy sortowania w akcji: od bąbelkowego do Shella

Sortowanie to pierwszy poważny algorytm, jaki spotyka każdy programista, i jednocześnie ostatni, który pisze samodzielnie w produkcji. Każdy język ma wbudowany sort, każdy jest lepszy od tego, co napiszesz wieczorem – a mimo to warto wiedzieć, co się dzieje pod spodem. Nie dlatego, że kiedyś zaimplementujesz sortowanie bąbelkowe w pracy (nie zaimplementujesz), ale dlatego, że algorytmy sortowania to najlepiej opisany fragment informatyki, na którym widać wszystko: kompromis czasu i pamięci, różnicę między przypadkiem średnim a pesymistycznym, stabilność, adaptacyjność i to, że asymptotyka bywa kłamstwem na małych danych.

Ten cykl ma cztery części. Zaczynamy od wyścigu i od algorytmów prostych, dalej będzie dziel i zwyciężaj, potem sortowania, które w ogóle nie porównują elementów, a na koniec – co naprawdę robi sorted(), std::sort i Arrays.sort, kiedy je wywołujesz.

Wyścig

Wszystkie tory dostają dokładnie tę samą, losowo wymieszaną tablicę 48 liczb i wykonują tyle samo operacji na klatkę animacji. To nie jest wykres złożoności – to prawdziwy wyścig, w którym ktoś przyjeżdża na metę pierwszy, a ktoś inny długo jeszcze przestawia słupki.

Kolejność na mecie jest zawsze taka sama, bo wejście jest zawsze takie samo (przyciskiem Nowe liczby wylosujesz inną tablicę, a listą obok zmienisz liczbę elementów). Liczby pod paskami to nie dekoracja – to realne liczniki. Dla tej konkretnej tablicy 48 elementów, w kolejności przyjazdu na metę:

Trzy rzeczy rzucają się w oczy od razu. Po pierwsze: dwa algorytmy wykonały zero porównań – i one wcale nie oszukują, tylko w ogóle nie działają na zasadzie „który element jest większy” (wrócę do tego w trzeciej części cyklu). Po drugie: sortowanie przez wybieranie zrobiło dokładnie tyle samo porównań co bąbelkowe, a mimo to przyjechało wcześniej niż wstawianie, które porównywało prawie dwa razy rzadziej – bo liczy się suma wszystkich operacji, a wybieranie prawie nic nie zapisuje. Po trzecie: różnica między najlepszym a najgorszym algorytmem porównawczym to tutaj raptem rząd wielkości – bo n = 48. Przy n = 48 000 ta sama różnica urosłaby do trzech rzędów wielkości i wyścig trzeba byłoby przerwać.

Czym to mierzymy

Zanim rozbierzemy algorytmy, cztery pojęcia, które będą wracać w całym cyklu.

Złożoność czasowa – jak rośnie liczba operacji wraz z n, zapisana w notacji dużego O. O(n²) znaczy: podwój dane, a pracy będzie czterokrotnie więcej. Zawsze pytaj, o który przypadek chodzi: średni, pesymistyczny czy optymistyczny – bo dla sortowania szybkiego są to trzy różne odpowiedzi.

Złożoność pamięciowa – ile pamięci ponad samą tablicę. Algorytm, któremu wystarczy kilka zmiennych, nazywamy sortującym w miejscu (in-place). Sortowanie przez scalanie potrzebuje dodatkowej tablicy wielkości n i to jest jego jedyna, ale realna wada.

Stabilność – czy elementy o równych kluczach zachowują pierwotną kolejność. Brzmi jak detal akademicki, dopóki nie posortujesz listy pracowników po nazwisku, potem po dziale i nie zobaczysz, że nazwiska w działach się rozjechały. Stabilny sort pozwala sortować wielokryterialnie przez sortowanie wielokrotne, od klucza najmniej istotnego do najważniejszego.

Adaptacyjność – czy algorytm wykorzystuje to, że dane są prawie posortowane. Sortowanie przez wstawianie na prawie gotowej tablicy działa niemal liniowo. Sortowanie przez wybieranie – nie, wykona swoje 1128 porównań niezależnie od tego, co dostanie. Ta jedna cecha decyduje o tym, że w prawdziwych bibliotekach wygrywa dziś TimSort, a nie czysty quicksort.

Sortowanie bąbelkowe

Bąbelkowe jest w każdym podręczniku, bo tłumaczy się w jednym zdaniu: przejdź tablicę od lewej do prawej i zamieniaj sąsiadów, którzy stoją w złej kolejności. Po pierwszym przebiegu największy element „wypłynął” na koniec jak bąbelek. Powtarzaj, aż nic się nie zmieni.

# Python
def bubble_sort(data):
    """Sortowanie bąbelkowe z wczesnym wyjściem, gdy przebieg nic nie zmienił."""
    items = list(data)
    for end in range(len(items) - 1, 0, -1):
        swapped = False
        for i in range(end):
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        if not swapped:          # tablica jest już uporządkowana
            break
    return items

Flaga swapped to jedyna rzecz, która ratuje ten algorytm z czystej rozpaczy: dzięki niej na już posortowanych danych bąbelkowe kończy po jednym przebiegu, czyli w O(n). W pozostałych przypadkach wykonuje n(n−1)/2 porównań: dla 24 elementów z animacji wyżej to 276, a po przełączeniu jej na 48 – dokładnie 1128, czyli tyle samo, ile pokazał licznik w otwierającym wyścigu. Jest stabilne, sortuje w miejscu i jest bezdyskusyjnie najgorszym rozsądnym wyborem w praktyce, bo tę samą pracę wykonuje przestawiając sąsiadów po jednym kroku.

Koktajlowe i grzebieniowe: dwie łatki na bąbelki

Bąbelkowe ma dwie znane słabości i do każdej powstała łatka.

Pierwsza to żółwie – małe elementy na końcu tablicy pełzną w lewo po jednej pozycji na przebieg. Odpowiedź: sortowanie koktajlowe (Cocktail Shaker), czyli bąbelkowe chodzące naprzemiennie w obie strony. Duże elementy jadą w prawo, małe wracają w lewo w tym samym cyklu.

# Python
def cocktail_sort(data):
    """Bąbelkowe naprzemiennie w obie strony – małe elementy nie pełzną już po jednym kroku."""
    items = list(data)
    lo, hi = 0, len(items) - 1
    swapped = True
    while swapped and lo < hi:
        swapped = False
        for i in range(lo, hi):              # w prawo: największe na koniec
            if items[i] > items[i + 1]:
                items[i], items[i + 1] = items[i + 1], items[i]
                swapped = True
        hi -= 1
        for i in range(hi, lo, -1):          # w lewo: najmniejsze na początek
            if items[i - 1] > items[i]:
                items[i - 1], items[i] = items[i], items[i - 1]
                swapped = True
        lo += 1
    return items

Druga słabość jest poważniejsza: porównywanie sąsiadów skazuje algorytm na kwadrat, bo jedna zamiana przesuwa element o jedno miejsce. Odpowiedź to sortowanie grzebieniowe (Comb Sort) – porównuj elementy odległe o gap, a odstęp zmniejszaj po każdym przebiegu, dzieląc go przez 1,3 (ta stała to wynik eksperymentów autorów, nie teorii).

# Python
def comb_sort(data):
    """Bąbelkowe z malejącym odstępem – dalekie zamiany likwidują żółwie."""
    items = list(data)
    gap, swapped = len(items), True
    while gap > 1 or swapped:
        gap = max(1, int(gap / 1.3))
        swapped = False
        for i in range(len(items) - gap):
            if items[i] > items[i + gap]:
                items[i], items[i + gap] = items[i + gap], items[i]
                swapped = True
    return items

Efekt jest zaskakująco duży – w wyścigu poniżej grzebieniowe zjeżdża z 1128 porównań do niecałych 450 i zostawia całą rodzinę bąbelków daleko w tyle. Ta sama sztuczka, zastosowana do sortowania przez wstawianie, da za chwilę algorytm Shella.

Czwarty tor to sortowanie gnoma – ciekawostka, którą warto znać dla samej idei: jedna pętla, jeden indeks, brak zagnieżdżeń. Gnom idzie w prawo; gdy trafi na parę w złej kolejności, zamienia ją i cofa się o krok. To sortowanie przez wstawianie przebrane za spacer.

# Python
def gnome_sort(data):
    """Jedna pętla, jeden indeks: krok w prawo, a po zamianie krok w tył."""
    items = list(data)
    i = 0
    while i < len(items):
        if i == 0 or items[i] >= items[i - 1]:
            i += 1
        else:
            items[i], items[i - 1] = items[i - 1], items[i]
            i -= 1
    return items

Sortowanie przez wybieranie

Przez wybieranie działa tak, jak człowiek układa karty na stole: znajdź najmniejszą, połóż na początku, powtórz dla reszty.

# Python
def selection_sort(data):
    """Znajdź minimum reszty i wstaw je na bieżącą pozycję – dokładnie n-1 zamian."""
    items = list(data)
    n = len(items)
    for i in range(n - 1):
        smallest = i
        for j in range(i + 1, n):
            if items[j] < items[smallest]:
                smallest = j
        if smallest != i:
            items[i], items[smallest] = items[smallest], items[i]
    return items

Liczba porównań jest sztywna: n(n−1)/2, zawsze, bez względu na dane. Za to zamian jest co najwyżej n−1 i to jest jego jedyny prawdziwy atut. Jeśli zapis jest drogi – pamięć flash, EEPROM, rekordy w wolnym magazynie – liczy się nie liczba porównań, tylko liczba przeniesień. W otwierającym wyścigu widać to jak na dłoni: bąbelkowe 1178 zapisów, przez wybieranie 86.

Sortowanie przez wybieranie w klasycznej postaci nie jest stabilne – zamiana odległych elementów potrafi przeskoczyć równy klucz. Da się je ustabilizować, ale wtedy trzeba przesuwać cały fragment tablicy i tracimy jedyną zaletę, czyli małą liczbę zapisów.

Sortowanie przez wstawianie

Przez wstawianie to sposób, w jaki układa się karty trzymane w ręce: bierzesz kolejną i wsuwasz ją w odpowiednie miejsce wśród już ułożonych.

# Python
def insertion_sort(data):
    """Kolejny element wsuwany w gotowy prefiks; przesuwamy, zamiast zamieniać."""
    items = list(data)
    for i in range(1, len(items)):
        current = items[i]
        j = i - 1
        while j >= 0 and items[j] > current:
            items[j + 1] = items[j]      # przesunięcie, nie zamiana (jeden zapis)
            j -= 1
        items[j + 1] = current
    return items

To najważniejszy algorytm z tej całej rodziny i jedyny z nich, który realnie pracuje w produkcji – bo jest stabilny, sortuje w miejscu, nie potrzebuje rekurencji i jest adaptacyjny. Na prawie posortowanych danych pętla while prawie się nie wykonuje i całość schodzi do O(n). Dla losowej tablicy 48 elementów z otwierającego wyścigu wstawianie potrzebowało 629 porównań; na tej samej tablicy z kilkoma przestawieniami – 175. Sortowanie przez wybieranie w obu przypadkach zrobi swoje 1128.

Dlatego właśnie każda poważna biblioteka ma w środku sortowanie przez wstawianie: dla krótkich fragmentów (zwykle poniżej 16–32 elementów) quicksort i mergesort przełączają się na nie, bo prosty algorytm bez rekurencji i z liniowym dostępem do pamięci po prostu wygrywa na małych danych. Do tego wątku wrócimy w drugiej i czwartej części cyklu.

Wariant binarny

Skoro prefiks jest już posortowany, miejsce wstawienia można znaleźć wyszukiwaniem binarnym zamiast liniowym. Liczba porównań spada wtedy do O(n log n), co jest ładne – ale liczba przesunięć zostaje kwadratowa, bo wstawienie w środek tablicy dalej wymaga przesunięcia ogona.

# Python
from bisect import insort

def binary_insertion_sort(data):
    """Miejsce wstawienia szukane binarnie; przesunięć dalej jest O(n²)."""
    result = []
    for value in data:
        insort(result, value)     # bisect.insort: wyszukiwanie binarne + wstawienie w miejsce
    return result

Ten wariant ma sens dokładnie wtedy, gdy porównanie jest drogie, a przesuwanie tanie – na przykład przy sortowaniu długich napisów porównywanych z uwzględnieniem lokalizacji. I nie jest to ciekawostka: dokładnie tak działa TimSort, gdy porządkuje swoje krótkie serie.

Sortowanie Shella

Donald Shell w 1959 roku zadał pytanie, które grzebieniowe zadało bąbelkowemu: skoro sortowanie przez wstawianie przesuwa elementy o jedno miejsce, to co, jeśli najpierw poukładamy je „z grubsza”, porównując elementy odległe o gap, a odstęp będziemy zmniejszać aż do jedynki?

# Python
GAPS = (701, 301, 132, 57, 23, 10, 4, 1)   # ciąg Ciury (2001), dobrany eksperymentalnie

def shell_sort(data):
    """Sortowanie przez wstawianie z malejącym odstępem między porównywanymi elementami."""
    items = list(data)
    n = len(items)
    for gap in (g for g in GAPS if g < n or g == 1):
        for i in range(gap, n):
            current = items[i]
            j = i
            while j >= gap and items[j - gap] > current:
                items[j] = items[j - gap]
                j -= gap
            items[j] = current
    return items

Ostatni przebieg z gap = 1 to zwykłe sortowanie przez wstawianie – ale wykonane na tablicy, która jest już prawie posortowana, więc dzięki adaptacyjności kosztuje grosze. Cała sztuka polega na tym, żeby wcześniejsze przebiegi wykonały tę pracę tanio.

Najciekawsze jest to, że nikt nie zna optymalnego ciągu odstępów. Oryginalny pomysł Shella (dziel przez 2) daje O(n²) w pesymistycznym przypadku. Ciąg Hibbarda (2^k−1) daje O(n^1,5), ciąg Sedgewicka O(n^4/3), a najlepszy znany praktycznie ciąg Ciury z 2001 roku – ten w kodzie wyżej – został po prostu znaleziony eksperymentalnie i nie ma dowodu na swoją złożoność. To rzadki przypadek algorytmu, w którym praktyka wyprzedziła teorię o kilkadziesiąt lat i wciąż jej nie oddała prowadzenia.

Shell nie jest stabilny (odległe zamiany psują kolejność równych kluczy), ale sortuje w miejscu, nie ma rekurencji i jest zaskakująco szybki dla średnich n. Dlatego trafia do miejsc, gdzie nie ma pamięci na bufory ani stosu na rekurencję – w tym do jądra Linuksa i do bibliotek systemów wbudowanych.

Kiedy O(n²) wygrywa

Wbrew tabelkom złożoności, algorytmy kwadratowe nie są bezużyteczne. Wygrywają w trzech sytuacjach:

1. Bardzo małe n. Notacja O ukrywa stałe, a te przy quicksorcie i mergesorcie są spore (rekurencja, bufory, wyliczanie pivota). Poniżej kilkunastu elementów sortowanie przez wstawianie po prostu jest szybsze i dlatego siedzi w środku każdej biblioteki.
2. Dane prawie posortowane. Wstawianie kosztuje wtedy O(n) i żaden ogólny algorytm nie zejdzie niżej.
3. Ekstremalne ograniczenia. Brak dodatkowej pamięci, brak stosu, drogie zapisy – wtedy liczy się prostota, a nie asymptotyka.

Poza tymi trzema przypadkami nie ma powodu, żeby ich używać. I dokładnie po to powstały algorytmy, o których będzie druga część cyklu: dziel i zwyciężaj, kopiec i te wszystkie hybrydy, które dziś naprawdę wykonują twój sorted().