Złożoność obliczeniowa algorytmów sortowania — tabela, notacja O i praktyka

Złożoność obliczeniowa algorytmu sortowania mówi, jak rośnie liczba wykonywanych operacji (głównie porównań i przestawień) oraz zużycie pamięci, gdy zwiększasz liczbę sortowanych elementów n. Proste algorytmy, takie jak sortowanie bąbelkowe czy przez wstawianie, mają złożoność O(n²), a wydajne — przez scalanie, kopcowanie i szybkie — O(n log n). Dla sortowania opartego na porównaniach O(n log n) to granica, której w najgorszym przypadku nie da się przebić.

Poniżej znajdziesz zbiorczą tabelę złożoności najważniejszych algorytmów, wyjaśnienie notacji O bez akademickiego żargonu i praktyczne wskazówki, który algorytm faktycznie działa w Twoim języku programowania.

Czym jest złożoność obliczeniowa algorytmów

Złożoność obliczeniowa to sposób opisu kosztu algorytmu niezależny od konkretnego komputera. Zamiast mierzyć milisekundy, które zależą od procesora, kompilatora i obciążenia systemu, liczy się, ile podstawowych operacji wykona algorytm dla danych o rozmiarze n — i jak ta liczba rośnie, gdy n rośnie.

Wyróżnia się dwa rodzaje złożoności:

• złożoność czasowa — liczba elementarnych kroków (w sortowaniu: porównań, zamian, przepisań elementów),
• złożoność pamięciowa — ilość dodatkowej pamięci potrzebnej poza samymi danymi wejściowymi.

Nie interesują nas dokładne liczby, tylko tempo wzrostu. Jeśli algorytm wykonuje 3n² + 5n + 20 operacji, to przy dużym n liczy się wyłącznie składnik n², więc mówimy, że ma złożoność O(n²). Stałe i składniki niższego rzędu pomija się, bo przy milionie elementów przestają mieć znaczenie.

Na tym, jak ten koszt przekłada się na rzeczywisty czas działania programu, skupia się osobny tekst o czasie wykonania programu (runtime).

Notacja O, Ω i Θ oraz przypadek pesymistyczny i średni

W analizie algorytmów używa się trzech oznaczeń asymptotycznych:

W codziennej praktyce programiści piszą „O” nawet wtedy, gdy formalnie chodzi o Θ — i tak też robi większość tabel, łącznie z tą poniżej.

Druga sprawa to rodzaj przypadku. Ten sam algorytm może zachowywać się zupełnie inaczej zależnie od danych:

• przypadek optymistyczny (najlepszy) — np. dane już posortowane,
• przypadek średni — dane w losowej kolejności,
• przypadek pesymistyczny (najgorszy) — dane ułożone najbardziej niekorzystnie dla danego algorytmu.

Kiedy ktoś mówi po prostu „złożoność quicksorta to O(n log n)”, ma na myśli przypadek średni. Pesymistyczny wynosi O(n²) — i ta różnica ma znaczenie, gdy dane może podsunąć atakujący albo gdy często sortujesz dane prawie uporządkowane.

Jak bardzo różnią się O(n²) i O(n log n)

Różnica jest ogromna i rośnie z rozmiarem danych. Dla n = 1 000 000 elementów:

• n² = 1 000 000 000 000 (bilion) operacji,
• n · log₂ n ≈ 1 000 000 · 20 = 20 000 000 operacji.

To mniej więcej pięćdziesiąt tysięcy razy mniej pracy. Dlatego algorytmy kwadratowe nadają się do małych tablic, a przy dużych zbiorach praktycznie się ich nie stosuje.

Tabela: złożoność obliczeniowa algorytmów sortowania

Zestawienie najczęściej omawianych algorytmów. „W miejscu” oznacza, że algorytm nie potrzebuje dodatkowej tablicy proporcjonalnej do n. „Stabilny” — że elementy o równych kluczach zachowują wzajemną kolejność.

* tylko w wersji z flagą, która kończy działanie, gdy w przebiegu nie było żadnej zamiany. ** przy założeniu, że dane są w miarę równomiernie rozłożone między kubełki.

Oznaczenia: n — liczba elementów, k — zakres wartości kluczy (lub liczba kubełków), d — liczba cyfr/pozycji klucza.

Algorytmy kwadratowe: bąbelkowe, przez wybór, przez wstawianie

Te trzy algorytmy są proste do zrozumienia i zaimplementowania, dlatego pojawiają się na każdych zajęciach z algorytmiki. Wszystkie mają złożoność O(n²) w przypadku średnim, bo dla każdego z n elementów wykonują pracę rzędu n.

Sortowanie bąbelkowe porównuje sąsiednie elementy i zamienia je, jeśli stoją w złej kolejności. Po każdym przebiegu największy element „wypływa” na koniec. W praktyce to najwolniejszy z tej trójki, bo wykonuje dużo zamian.

Sortowanie przez wybór w każdym kroku szuka minimum w nieposortowanej części i stawia je na właściwym miejscu. Zawsze wykonuje około n²/2 porównań, niezależnie od danych, ale tylko n − 1 zamian — co bywa zaletą, gdy zapis do pamięci jest drogi.

Sortowanie przez wstawianie bierze kolejny element i wsuwa go w odpowiednie miejsce posortowanego już fragmentu. Dla danych prawie posortowanych działa niemal liniowo, a przy małych tablicach (kilkanaście–kilkadziesiąt elementów) jest szybsze od algorytmów O(n log n) dzięki prostocie i dobremu wykorzystaniu pamięci podręcznej procesora. Właśnie dlatego hybrydy, takie jak Timsort czy introsort, używają go do sortowania krótkich fragmentów.

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:   # przesuwamy większe elementy w prawo
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

Dwie zagnieżdżone pętle, z których każda w najgorszym przypadku przechodzi przez całą tablicę, to klasyczny sygnał złożoności O(n²).

Algorytmy O(n log n): scalanie, kopcowanie, quicksort

Algorytmy z tej grupy opierają się na podziale problemu na mniejsze części (dziel i zwyciężaj) albo na strukturze danych, która pozwala szybko wybierać kolejne elementy.

Sortowanie przez scalanie

Tablicę dzieli się na pół, rekurencyjnie sortuje obie połowy, a potem scala je w jedną posortowaną całość. Podziałów jest log₂ n, a na każdym poziomie scalanie kosztuje O(n) — stąd O(n log n), i to gwarantowane w każdym przypadku. Ceną jest dodatkowa pamięć O(n) na bufor przy scalaniu tablic. Merge sort jest stabilny i świetnie nadaje się do sortowania list wiązanych oraz danych, które nie mieszczą się w pamięci (sortowanie zewnętrzne, stosowane m.in. przez systemy baz danych przy dużych operacjach ORDER BY).

Sortowanie przez kopcowanie

Heap sort buduje z tablicy kopiec (binarny kopiec maksymalny) w czasie O(n), a następnie n razy zdejmuje największy element, za każdym razem naprawiając kopiec w O(log n). Daje to gwarantowane O(n log n) i jednocześnie O(1) dodatkowej pamięci. W praktyce jest zwykle wolniejszy od dobrze zaimplementowanego quicksorta, bo skacze po pamięci i gorzej korzysta z cache procesora. Nie jest stabilny.

Sortowanie szybkie (quicksort)

Quicksort wybiera element osiowy (pivot), dzieli tablicę na elementy mniejsze i większe od niego, a potem rekurencyjnie sortuje obie części. Gdy pivot dzieli dane mniej więcej po równo, głębokość rekurencji wynosi log n i całość kosztuje O(n log n).

Problem pojawia się przy złym wyborze pivota — np. gdy zawsze bierzesz pierwszy element, a dane są już posortowane. Wtedy każdy podział odcina tylko jeden element, rekurencja ma głębokość n, a złożoność rośnie do O(n²). Sposoby obrony:

1. losowy wybór pivota,
2. mediana z trzech (pierwszy, środkowy i ostatni element),
3. przełączenie się na heap sort, gdy rekurencja robi się zbyt głęboka — tak działa introsort.

Wskazówka: Jeśli implementujesz quicksorta sam, zawsze wywołuj rekurencję najpierw dla mniejszej części, a większą obsługuj w pętli. Dzięki temu głębokość stosu nie przekroczy O(log n) nawet w pechowym przypadku.

Dlaczego nie da się sortować szybciej niż O(n log n)

Każdy algorytm, który porządkuje dane wyłącznie przez porównywanie par elementów, potrzebuje w najgorszym przypadku Ω(n log n) porównań. Uzasadnienie opiera się na drzewie decyzyjnym: n elementów można ułożyć na n! sposobów, a każde porównanie daje jedną z dwóch odpowiedzi. Żeby rozróżnić wszystkie n! permutacji, drzewo musi mieć wysokość co najmniej log₂(n!), a ta wartość rośnie jak n log n.

Wniosek praktyczny: merge sort i heap sort są asymptotycznie optymalne wśród sortowań porównujących. Kolejne usprawnienia dotyczą już stałych, wykorzystania pamięci podręcznej i zachowania na typowych danych, a nie samej klasy złożoności.

Sortowanie liniowe: zliczanie, pozycyjne, kubełkowe

Granicę n log n można obejść, jeśli wiesz coś więcej o kluczach. Sortowanie przez zliczanie dla liczb całkowitych z zakresu 0…k liczy wystąpienia każdej wartości i odtwarza tablicę w czasie O(n + k). Opłaca się, gdy k jest porównywalne z n — np. sortujesz milion ocen w skali 1–6. Przy kluczach 64-bitowych tablica liczników byłaby absurdalnie duża.

Sortowanie pozycyjne (radix sort) stosuje stabilne sortowanie przez zliczanie kolejno do cyfr klucza (np. bajtów), co daje O(d · (n + k)). Sortowanie kubełkowe rozkłada dane do przedziałów i sortuje każdy osobno — działa liniowo tylko wtedy, gdy dane są równomiernie rozłożone.

Jakie sortowanie używa Twój język programowania

W kodzie produkcyjnym prawie nigdy nie piszesz sortowania od zera. Biblioteki standardowe używają dopracowanych algorytmów hybrydowych:

Timsort wykorzystuje to, że prawdziwe dane często zawierają już posortowane fragmenty (tzw. runy). Dla tablicy w całości uporządkowanej działa w O(n), co jest ogromną przewagą nad klasycznym quicksortem. Więcej o samym PHP przeczytasz we wprowadzeniu do PHP, a o projektowaniu kodu w Javie — w tekście o wzorcach projektowych Java.

Jeśli chcesz porównać algorytmy na własnym komputerze, mierz czas, a nie wierz cudzym tabelkom — wyniki silnie zależą od danych, języka i sprzętu:

import random, timeit

data = [random.randint(0, 10**6) for _ in range(10_000)]

t_builtin = timeit.timeit(lambda: sorted(data), number=10)
t_insertion = timeit.timeit(lambda: insertion_sort(data.copy()), number=1)

print(f"sorted():        {t_builtin / 10:.4f} s na przebieg")
print(f"insertion_sort:  {t_insertion:.4f} s na przebieg")

Spróbuj powtórzyć pomiar dla 1000, 10 000 i 20 000 elementów. Przy algorytmie O(n²) dwukrotne zwiększenie n mniej więcej czterokrotnie wydłuża czas, przy O(n log n) — nieco ponad dwukrotnie.

Który algorytm sortowania wybrać

• Ogólny przypadek, dane w pamięci: wbudowana funkcja sortująca języka. Jest szybsza i lepiej przetestowana niż cokolwiek, co napiszesz w godzinę.
• Potrzebujesz zachować kolejność równych elementów (np. sortujesz zamówienia po dacie, a wcześniej były posortowane po kliencie): wybierz sortowanie stabilne — Timsort, merge sort, std::stable_sort, sort.Stable.
• Twarda gwarancja czasu i brak dodatkowej pamięci (systemy wbudowane, czas rzeczywisty): heap sort.
• Bardzo małe tablice lub dane prawie posortowane: sortowanie przez wstawianie.
• Liczby całkowite z niewielkiego zakresu albo klucze o stałej długości: sortowanie przez zliczanie lub pozycyjne.
• Dane większe niż pamięć RAM: zewnętrzne sortowanie przez scalanie — dzielisz plik na kawałki, sortujesz każdy w pamięci, a potem scalasz.

Sortowanie bąbelkowe i przez wybór warto znać, bo dobrze ilustrują pojęcie złożoności, ale w realnym kodzie praktycznie nie mają zastosowania.