Algorytmy sortowania — porównanie bubble sort, merge sort i quick sort

Algorytm sortowania przestawia te same elementy do określonego porządku, na przykład od najmniejszego do największego. Jeśli chcesz najkrótszą odpowiedź od razu: bubble sort jest prosty, ale zwykle zbyt wolny dla dużych list, merge sort daje przewidywalną wydajność $O(n \log n)$, a quick sort często działa szybko w praktyce, gdy podziały pozostają w miarę zrównoważone.

Właściwe pytanie nie brzmi „który algorytm sortowania jest najlepszy?”, lecz „najlepszy w jakich warunkach?”. Bubble sort dobrze pokazuje lokalne zamiany, merge sort jasno ilustruje strategię dziel i zwyciężaj, a quick sort pokazuje, dlaczego średni czas działania może być bardzo dobry nawet bez gwarancji w najgorszym przypadku.

Co robią algorytmy sortowania

Dla listy takiej jak $[5, 1, 4, 2]$ algorytm powinien zwrócić te same wartości w uporządkowanej kolejności:

$$[1, 2, 4, 5]$$

Brzmi to prosto, ale różne algorytmy dochodzą do tego wyniku na bardzo różne sposoby. Główne różnice dotyczą:

• sposobu przemieszczania elementów
• liczby porównań lub zamian, których zwykle używają
• ilości dodatkowej pamięci, jakiej potrzebują
• wrażliwości na niekorzystne układy danych wejściowych

Bubble sort: powtarzane zamiany sąsiadów

Bubble sort przechodzi przez listę i zamienia sąsiednie elementy, które są w złej kolejności. Po jednym pełnym przebiegu największy nieposortowany element „wypływa” na koniec.

Dla $[5, 1, 4, 2]$ pierwszy przebieg wygląda tak:

$$[5, 1, 4, 2] \to [1, 5, 4, 2] \to [1, 4, 5, 2] \to [1, 4, 2, 5]$$

Następnie algorytm powtarza to dla pozostałej nieposortowanej części, aż żadna zamiana nie będzie już potrzebna.

Bubble sort jest przydatny głównie do nauki. Ogólnie ma złożoność czasową $O(n^2)$, więc liczba porównań szybko rośnie wraz z rozmiarem listy. Dla małych przykładów na lekcji to wystarcza. Do poważniejszych zastosowań sortowania zwykle nie jest to dobry wybór.

Merge sort: podziel, posortuj, potem scal

Merge sort wykorzystuje strategię dziel i zwyciężaj. Dzieli listę na mniejsze części, sortuje te części, a potem scala posortowane fragmenty z powrotem.

Dla $[5, 1, 4, 2]$ można to jasno przedstawić tak:

$$[5, 1, 4, 2] \to [5, 1] + [4, 2]$$

Posortuj każdą połowę:

$$[5, 1] \to [1, 5], \qquad [4, 2] \to [2, 4]$$

Następnie scal dwie posortowane połówki:

$$[1, 5] + [2, 4] \to [1, 2, 4, 5]$$

Główną zaletą merge sort jest przewidywalność. W typowej analizie jego czas działania wynosi $O(n \log n)$, a nie tylko średnio. Główny koszt to pamięć: typowe implementacje tablicowe używają dodatkowego miejsca podczas scalania.

Quick sort: podział względem pivota

Quick sort także korzysta ze strategii dziel i zwyciężaj, ale w inny sposób. Wybiera pivot, umieszcza mniejsze elementy po jednej stronie, a większe po drugiej, a następnie rekurencyjnie sortuje obie strony.

Przy użyciu pivota $4$ dla $[5, 1, 4, 2]$ jeden możliwy podział to:

$$[1, 2] \;|\; 4 \;|\; [5]$$

Teraz lewa i prawa część są znacznie mniejsze, więc sortowanie szybko się kończy.

Quick sort często działa szybko w praktyce, ponieważ wiele implementacji wykonuje podział w miejscu i szybko zmniejsza problem, gdy pivot dzieli listę dość dobrze. Ale ten warunek ma znaczenie. Jeśli wybory pivota są wielokrotnie słabe, na przykład ciągle tworzą jedną bardzo małą część i jedną prawie pełną, to najgorszy przypadek staje się $O(n^2)$.

Bubble sort vs merge sort vs quick sort

Algorytm	Główna idea	Typowy czas	Czas w najgorszym przypadku	Dodatkowa pamięć
Bubble sort	Powtarzane zamiany sąsiednich elementów	$O(n^2)$	$O(n^2)$	Mała
Merge sort	Podział, sortowanie połówek, scalanie	$O(n \log n)$	$O(n \log n)$	Większa w typowych implementacjach tablicowych
Quick sort	Podział względem pivota	Często $O(n \log n)$	$O(n^2)$	Często mniejsza niż w merge sort

Jeśli chcesz zapamiętać jedną praktyczną rzecz, to jest ona taka: bubble sort to algorytm do nauki, merge sort to stabilna i przewidywalna opcja, a quick sort często jest praktycznym wyborem pod względem szybkości, gdy implementacja dobrze radzi sobie z wyborem pivota.

Jeden przykład na tej samej liście

Użyj tej samej listy:

$$[5, 1, 4, 2]$$

Bubble sort stale poprawia lokalne błędy. Nie „widzi” całej struktury, więc może potrzebować wielu przebiegów.

Merge sort najpierw rozbija problem na mniejsze posortowane części, a potem je łączy. To właśnie dlatego jego wydajność pozostaje przewidywalna wraz ze wzrostem rozmiaru listy.

Quick sort próbuje wcześnie wykonać jeden mocny podział. Jeśli podział jest wystarczająco zrównoważony, reszta pracy szybko się zmniejsza.

Dlatego uczniowie często lepiej zapamiętują liczby opisujące złożoność po zobaczeniu, jak jedna lista przechodzi przez każdą z tych metod. Te liczby nie są przypadkowymi etykietami. Odzwierciedlają to, jak algorytm zmniejsza nieuporządkowanie.

Częste błędy przy porównywaniu algorytmów sortowania

Zakładanie, że quick sort jest zawsze szybszy

Quick sort często jest szybki w praktyce, ale nie ma gwarancji, że będzie najszybszy w każdym przypadku. Zły wybór pivota może mu bardzo zaszkodzić.

Traktowanie algorytmów $O(n \log n)$ jako identycznych

Merge sort i quick sort mogą mieć ten sam średni rząd wzrostu, a mimo to różnić się zużyciem pamięci, gwarancjami dla najgorszego przypadku i szczegółami implementacji.

Używanie bubble sort tylko dlatego, że łatwo go zakodować

Łatwość kodowania to nie to samo co przydatność. Do małych demonstracji bubble sort jest w porządku. Dla większych rzeczywistych danych zwykle wykonuje niepotrzebną pracę.

Pomijanie modelu danych wejściowych

Te porównania zwykle zakładają sortowanie porównawcze dla ogólnych danych wejściowych. Jeśli dane mają szczególną strukturę, sortowania nieporównawcze, takie jak counting sort, mogą całkowicie zmienić decyzję.

Kiedy używa się poszczególnych algorytmów sortowania

Bubble sort jest używany głównie do nauczania, śledzenia działania algorytmu i bardzo małych przykładów, gdzie przejrzystość jest ważniejsza niż wydajność.

Merge sort stosuje się wtedy, gdy ważne jest stabilne zachowanie $O(n \log n)$ i można zaakceptować dodatkową pamięć. Jest też naturalnym wyborem dla list wiązanych oraz w sytuacjach, gdzie znaczenie ma stabilne sortowanie, zależnie od implementacji.

Quick sort stosuje się wtedy, gdy ważna jest praktyczna szybkość, a implementacja ma dobrą strategię wyboru pivota lub zabezpieczenia awaryjne. Wiele strategii sortowania w bibliotekach standardowych wykorzystuje idee quick sort wraz z zabezpieczeniami, zamiast naiwnej wersji podręcznikowej.

Szybki sposób na zapamiętanie różnicy

Zapamiętaj je przez ruch:

• bubble sort poprawia sąsiadów
• merge sort buduje posortowane połówki
• quick sort dzieli względem pivota

Taki obraz mentalny jest bardziej użyteczny niż zapamiętywanie trzech nazw i trzech wzorów.

Spróbuj własnej wersji

Weź listę $[7, 3, 6, 1]$ i prześledź jeden przebieg bubble sort, jeden cykl podziału i scalania w merge sort oraz jeden podział względem pivota w quick sort. Jeśli potrafisz wyjaśnić, dlaczego lista zmienia się inaczej w każdym przypadku, to znaczy, że rozumiesz już tę ideę.