Algorytmy sortujące wizualizowane: od Bubble do Radix Sort…

Niski graniczny zakres dla algorytmów sortujących opartych na porównaniach

Algorytm sortujący oparty na porównaniach decyduje o porządku wyłącznie poprzez porównywania par elementów. Istnieje n! możliwych uporządkowań n elementów, a drzewo decyzyjne binarne rozróżniające wszystkie te uporządkowania musi mieć wysokość co najmniej ⌈log₂(n!)⌉, które według aproksymacji Stirlinga wynosi Θ(n log n). To jest trudny graniczny zakres informacyjny: dowolny algorytm sortujący oparty na porównaniach wymaga co najmniej Ω(n log n) porównań w najgorszym przypadku. Algorytmy mergesort i heapsort osiągają ten zakres w najgorszym przypadku; quicksort osiąga go tylko średnio, a przy przeciwnikowym wejściu degradowa się do O(n²). Sortowanie stabilne zachowuje względny porządek elementów równych — sortowanie według nazwiska powinno utrzymać Johna Smitha występującego wcześniej niż Jane Smith.

Sorty o złożoności O(n²) i podział na podzadki

Algorytm wstawiania ma złożoność O(n) dla prawie posortowanych danych i jest odpowiednim wyborem dla małych tablic lub danych przychodzących online, jeden element po drugim. Sortowanie łączeniowe dzieli tablicę na pół, rekurencyjnie sortuje każde z pół, a następnie łączy je: T(n) = 2T(n/2) + O(n), co daje gwarancji O(n log n) w najlepszym, średnim i najgorszym przypadku. Jest ono stabilne, ale nie jest sortowaniem miejscowym — wymaga O(n) przestrzeni dodatkowej. Sortowanie łączeniowe w Pythonie (Timsort) i sortowanie tablic w Javie (Arrays.sort) używają wariantu od dołu, który łączy już istniejące posortowane sekwencje, co daje O(n) dla prawie posortowanych danych wejściowych. Algorytm quicksort dzieli tablicę na podzadki wokół punktu odniesienia: średnio O(n log n) z dobrym punktem odniesienia, O(n²) najgorszym przypadkiem dla posortowanej tablicy z złym punktem odniesienia — ta sytuacja może być zmniejszona poprzez wybor punktu odniesienia jako mediany trzech elementów, losowe punkty odniesienia lub przeprowadzanie sortowania kopcowego przez Introsort po przekroczeniu pewnego próg głębokości rekurencji (używane w sortowaniu std::sort w C++).

Algorithm    Best        Average     Worst       Space   Stable  In-place
Insertion    O(n)        O(n²)       O(n²)       O(1)    Yes     Yes
Merge        O(n log n)  O(n log n)  O(n log n)  O(n)    Yes     No
Quicksort    O(n log n)  O(n log n)  O(n²)       O(log n) No     Yes
Heap Sort    O(n log n)  O(n log n)  O(n log n)  O(1)    No      Yes
Counting     O(n+k)      O(n+k)      O(n+k)      O(k)    Yes     No
Radix (LSD)  O(dn)       O(dn)       O(dn)       O(n+k)  Yes     No

Sortowanie kopcowe i przekraczanie granicy porównawczej

Sortowanie kopcowe tworzy dwuczynnikowy maksymalny kopiec w czasie O(n) (kopiec zbudowany metodą Floyd'a, nie n osobnych wstawień), a następnie wielokrotnie odcina maksimum w czasie O(log n) na krok, zagwarantowując O(n log n) w najgorszym przypadku z dodatkowym przestrzenią O(1) — ale jest to niezawodne i jego schemat dostępu losowy sprawia, że w praktyce jest 2–5 razy wolniejsze od sortowania szybkiego ze względu na braki w buforach. Algorytmy unikające porównań mogą uciec się z granicy n log n: sortowanie liczeniowe liczy wystąpienia w danym zakresie [0,k] i oblicza sumy częściowe, co daje O(n+k); sortowanie radyczne stosuje stabilne sortowanie liczeniowe do każdej pozycji cyfry od najmniej znaczącej do najbardziej znaczącej, co daje O(d·(n+k)), a jest to główna metoda w sortowaniu na karcie graficznej i w rozproszonym sortowaniu; sortowanie butelek rozrzuca równorodnie rozłożone liczby zmiennoprzecinkowe do n butel, co daje O(n) oczekiwane.

Często zadawane pytania

Dlaczego żaden algorytm oparty na porównaniach nie może pokonać O(n log n)?

Algorytm oparty na porównaniach decyduje o porządku wyłącznie poprzez porównywania par elementów. Istnieje n! możliwych uporządkowań n elementów, a drzewo binarne rozróżniające je musi mieć wysokość co najmniej ⌈log2(n!)⌉, które zgodnie z aproksymacją Stirlinga wynosi Θ(n log n). To jest trudny graniczną punkt informacyjny — żaden algorytm oparty na porównaniach, nawet bardzo inteligentny, nie może go pokonać w najgorszym przypadku.

Jak algorytmy sortujące przez liczenie i radiksowe pokonują granicę O(n log n)?

Skakają całkowicie nad granicą, ponieważ nigdy nie porównują dwóch elementów bezpośrednio. Algorytm sortujący przez liczenie liczy wystąpienia każdego wartości w znanym zakresie [0,k] i oblicza sumy przedrostkowe, działając w czasie O(n+k). Algorytm radiksowy stosuje stabilny algorytm sortujący przez liczenie do każdego położenia cyfry od najmniejszego do najważniejszego, działając w czasie O(d·(n+k)) — oba są ograniczone do kluczy strukturalnych, takich jak liczby całkowite z ograniczonym zakresem, a nie dowolnych porównywalnych obiektów.

Co oznacza, że algorytm sortujący jest stabilny?

Stabilny sortowanie zachowuje relatywną kolejność elementów, które porównują się jako równe — na przykład, sortowanie według nazwiska powinno utrzymać Johna Smitha przed Jane Smithem, jeśli były już w takiej kolejności. Sortowanie przez scalanie, sortowanie przez wstawianie, sortowanie zastępujące, sortowanie przez liczenie i radiksowe są wszystkie stabilne; quicksort i heap sort nie są stabilne, ponieważ wykonywane są wymiernie długosći wymiana, które mogą zmieniać kolejność równych elementów.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Sorting Algorithms Visualizer — Bubble, Quick, Merge, Heap i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Sorting Algorithms Visualizer — Bubble, Quick, Merge, Heap