Algorytmy sortujące: Porównanie bąbelkowego, szybkiego, łączenia i kopcowego

Porządkowanie algorytmami porównującymi ma granicę

Każdy algorytm sortujący, który decyduje o porządku poprzez porównywanie par elementów — co obejmuje każdą metodę z tego artykułu — nie może w najgorszym przypadku przewyższyć O(n log n) porównań, ze względu na czysto informacyjny powód: istnieje n! możliwych kolejności n elementów, każde porównanie ma tylko dwa wyniki, a rozróżnienie między n! możliwościami wymaga co najmniej log₂(n!) ≈ n·log₂(n) porównań, zgodnie z aproksymacją Stirlinga. Ten jedyny limit służy jako standard, według którego wszystkie algorytmy poniżej są oceniane — niektóre osiągają go, inne nie, a te, które nie osiągnąły tego limitu, nie są proste implementacje tej samej idei, ale stanowią podstawowe różnice w zrównoważeniach.

O(n²): prosty, ale prawdopodobnie nie nadający się do tego zadania

Algorytm bąbelkowy powtarza przejście po tablicy zamieniając parę elementów siedzących obok siebie, które są w złym porządku, aż nic już nie przestanie się ruchem; algorytm wstawiania buduje obszerną sekcję uporządkowaną stopniowo, wstawiając każdy nowy element na jego prawidłowe miejsce wśród już uporządkowanych prefiksów; algorytm wyboru powtarza znalezienie minimum z nieuporządkowanej części reszty i zamianę go na swoje miejsce. Wszystkie trzy są O(n²) w najgorszym przypadku — około 500 miliardów operacji dla miliona elementów, co jest bezlitosnie wolne — a żaden z nich nie powinien być używany na dużych zbiorach rzeczywistych danych. Algorytm wstawiania otrzymuje prawdziwe wyjątki: dla niemal uporządkowanych danych działa prawie O(n), ponieważ każdy nowy element potrzebuje bardzo mało zamian, aby znaleźć swoje miejsce, co dokładnie jest powodem, dla którego implementacje sortowania produkcyjnych (Timsort, IntroSort) przełączają się na algorytm wstawiania dla małych podtablic lub niemal uporządkowanych sekwencji zamiast rekurencyjnie spadając do końca.

Sortowanie łączeniem: gwarantowane n log n za cenę pamięci

Sortowanie łączeniem dzieli tablicę na połowy rekurencyjnie do pojedynczych elementów, a następnie łączy posortowane półtablice w czasie liniowym na każdym poziomie:

sortMerge(arr): if długość(arr) <= 1: zwróć arr mid = długość(arr) / 2 lewo = sortMerge(slice(arr, 0, mid)) prawo = sortMerge(slice(arr, mid, długość(arr))) zwróć łączenie(lewo, prawo) // liniowe łączenie dwóch posortowanych tablic Sortowanie łączeniem gwarantuje O(n log n) w każdym przypadku — najlepszym, średnim i najgorszym. Jest stabilne (elementy równe pozostają w oryginalnej kolejności relacyjnej, co ma znaczenie przy sortowaniu rekordów według jednego pola, podczas gdy inne pole decyduje o porządku w przypadku remisów). Kosztem jest pamięć: krok łączenia wymaga O(n) przestrzeni dodatkowej, dlatego w kontekście z ograniczoną dostępnością pamięci często wybierane są inne algorytmy mimo gwarancji najgorszego przypadku sortowania łączeniem.

mergeSort(arr):
  if len(arr) <= 1: return arr
  mid = len(arr) / 2
  left  = mergeSort(arr[:mid])
  right = mergeSort(arr[mid:])
  return merge(left, right)     // linear-time merge of two sorted arrays

Quicksort: najczęściej szybki, czasem strasznie wolny

Quicksort wybiera punkt odniesienia, podzielić tablicę tak, aby wszystko mniejsze niż punkt odniesienia znalazło się po lewej stronie, a wszystko większe — po prawej stronie, a następnie rekurencyjnie sortuje obie strony. Srednio jego złożoność wynosi O(n log n) z bardzo dobrymi stałymi — w praktyce Quicksort zwykle wygrywa z Sortowaniem Łączeniem dla losowych danych, ponieważ sortuje na miejscu i ma lepszą lokalizację w pamięci — ale jego najgorszy przypadek to O(n²), który występuje wtedy, gdy wybór punktu odniesienia spowoduje ciągłe podział tablicy na podtablice o rozmiarach 1 i (n-1) zamiast dwóch prawie równych połowy. Prosta strategia wyboru punktu odniesienia „zawsze pierwszy element” napotka ten najgorszy przypadek dla danych uporządkowanych, co dokładnie jest typą danych rzeczywistych, najczęściej widzianych — powód, dla którego produkcyjne Quicksorty używają zastosowania losowego lub mediany trzech jako strategii wyboru punktu odniesienia.

Sortowanie kopcowe: gwarancja worst-case szybkości Quicksorta bez dodatkowej pamięci

Sortowanie kopcowe najpierw uporządkowuje tablicę w kopiec binarny maksymalny (każdy rodzic jest co najmniej taki sam jak jego dzieci, tworzony w czasie O(n)), a następnie wielokrotnie wymienia korzeń kopca — zawsze bieżący maksimum — na koniec nieuporządkowanej części i ponownie uporządkowuje to, co zostało, w czasie O(log n) na wydzielanie. To daje gwarancji worst-case O(n log n), miejscowo, bez dodatkowej pamięci — stricte lepsze zachowanie worst-case niż Quicksort i mniej pamięci niż sortowanie łączeniowe — ale utraci na rzeczywistej szybkości w stosunku do Quicksorta ze względu na to, że operacje kopcowe skaczą po tablicy niezależnie od kolejności, co jest znacznie mniej przyjazne dla bufora pamięci niż mostly-sequential partitioning Quicksorta.

Co rzeczywiście pokazują kolumny i tony

Na tej stronie każdy algorytm sortuje taką samą początkową tablicę wysokości kolumn, gdzie każda porównanie i zamiana mapowana jest na osobny dźwięk za pomocą Web Audio API. Dlatego algoritmy o złożoności O(n²), takie jak bąbelkowy sort, są słysząco oraz widocznie przetwarzane znacznie więcej operacji niż łączeniowy sort lub szybki sort na tym samym wejściu. Obserwacja krótkookresowych zamian sąsiednich kolumn w bąbelkowym sortowaniu w porównaniu do długookresowych skoków podziału w szybkim sortowaniu, a także czystego przebiegu zdominowanego przez podział i zwycięstwo w łączeniowym sortowaniu, sprawia, że różnice między tymi schematami dostępu — nie tylko ich liczby operacji — są bezpośrednio widoczne. Notacja O na stronie nigdy nie przekazuje tego tak wyraźnie.

Często zadawane pytania

Wypróbuj na żywo

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