📊 Algorytmy sortowania — obraz i dźwięk

Niebieskie słupki są nieposortowane, pomarańczowy oznacza elementy aktualnie porównywane, czerwony oznacza trwającą zamianę, fioletowy to pivot lub element kluczowy, cyjan to nadpisanie (używane przez merge, counting i radix sort), a zielone słupki są potwierdzone jako znajdujące się na ostatecznej posortowanej pozycji.

Za każdym razem, gdy algorytm dotyka słupka, odtwarzany jest krótki dźwięk fali trójkątnej, którego częstotliwość jest logarytmicznie mapowana na wartość tego słupka. Niskie słupki brzmią nisko, a wysokie słupki brzmią wysoko, więc posortowana tablica tworzy płynnie rosnącą skalę — słyszalny sygnał porządku wyłaniającego się z chaosu.

Dla danych losowych quick sort, merge sort i heap sort (wszystkie ze średnią O(n log n)) są znacznie szybsze niż metody O(n²), takie jak bubble czy selection sort. Dla kluczy całkowitych w małym zakresie sortowania bez porównań (counting w O(n+k), radix w O(nk)) mogą być jeszcze szybsze, ponieważ omijają dolne ograniczenie O(n log n) dla sortowań opartych na porównaniach.

Quick sort ma średnią złożoność O(n log n), ale w najgorszym przypadku degraduje się do O(n²) — zwykle gdy pivot wielokrotnie okazuje się najmniejszym lub największym elementem, co może się zdarzyć przy już posortowanych lub celowo złośliwych danych wejściowych. Rzeczywiste implementacje łagodzą to poprzez losowy wybór pivota lub metodę mediany z trzech.

Merge sort zawsze działa w czasie O(n log n) niezależnie od danych wejściowych i jest sortowaniem stabilnym, ale potrzebuje O(n) dodatkowej pamięci do scalania podtablic. Quick sort sortuje w miejscu, zużywając mniej pamięci, i w praktyce jest zwykle szybszy dzięki lepszemu zachowaniu pamięci podręcznej, ale nie jest stabilny i ma ten najgorszy przypadek O(n²).

Nie są oparte na porównaniach. Counting sort zlicza, ile razy występuje każda wartość, i odtwarza tablicę bezpośrednio, działając w O(n+k), gdzie k to zakres wartości. Radix sort przetwarza liczby cyfra po cyfrze, wykorzystując stabilny przebieg kubełkowy. Ponieważ nigdy nie porównują dwóch elementów ze sobą, dolne ograniczenie dla porównań ich nie dotyczy.

Sortowanie stabilne zachowuje względną kolejność elementów, które są sobie równe. Ma to znaczenie przy sortowaniu rekordów według wielu kluczy — na przykład sortowanie według nazwiska, a następnie stabilne sortowanie według daty zachowuje alfabetyczną kolejność wpisów z tą samą datą. Merge, insertion i counting sort są stabilne; quick, heap i selection sort zazwyczaj nie są.

Sortowania kwadratowe, takie jak bubble, gnome i cocktail-shaker sort, są rzadko używane w produkcji, ale są doskonałymi narzędziami dydaktycznymi: ich prosta logika czyni mechanikę porównania i zamiany oczywistą, a obserwowanie, jak powoli przechodzą przez dużą tablicę, daje intuicyjne wyczucie, dlaczego złożoność algorytmiczna ma znaczenie.

Tak. Na bardzo małych tablicach narzut stałego czynnika sprytnych algorytmów może sprawić, że proste metody, takie jak insertion sort, staną się konkurencyjne — dlatego wiele rzeczywistych bibliotek przełącza się na insertion sort poniżej pewnego progu. Wraz ze wzrostem tablicy metody O(n log n) zdecydowanie wysuwają się na prowadzenie, a różnica dramatycznie się powiększa.

Tak, podstawowe idee są identyczne. Większość bibliotek standardowych języków używa hybrydowych sortowań — na przykład Timsort (hybryda merge/insertion) w Pythonie i sortowaniu obiektów w Javie, oraz introsort (quick sort z awaryjnym przejściem na heap sort) w C++. Ta wizualizacja pokazuje podręcznikowe elementy składowe, z których zbudowane są te produkcyjne sortowania.