Sortowanie przez scalanie

Sortowanie przez scalanie

Przykład działania
Rodzaj	Sortowanie
Struktura danych	Tablica, lista
Złożoność
Czasowa	$O(n\cdot \log(n))$
Pamięciowa	$O(n)$

Sortowanie przez scalanie w wersji rekurencyjnej

Sortowanie przez scalanie (ang. merge sort) – rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi.

Algorytm

Wyróżnić można trzy podstawowe kroki:

1. Podział zestawu danych na dwie równe części.
2. Zastosowanie sortowania przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element.
3. Połączenie posortowanych podciągów w jeden posortowany ciąg.

W pseudokodzie algorytm można zapisać następująco:

SORT-SCAL(T, p, r):
    JEŚLI p < r:
        q → (p+r)/2
        SORT-SCAL(T, p, q)
        SORT-SCAL(T, q+1, r)
        SCALANIE(T, p, q, r)

Procedura scalania dwóch ciągów $A[1,\dots ,n]$ i $B[1,\dots ,m]$ do ciągu $C[1,\dots ,m+n]$:

1. Utwórz wskaźniki na początki ciągów $A$ i $B$ → $i=1,$ $j=1.$
2. Jeżeli ciąg $A$ wyczerpany $(i>n),$ dołącz pozostałe elementy ciągu $B$ do $C$ i zakończ pracę.
3. Jeżeli ciąg $B$ wyczerpany $(j>m),$ dołącz pozostałe elementy ciągu $A$ do $C$ i zakończ pracę.
4. Jeżeli $A[i]\leqslant B[j]$ dołącz $A[i]$ do $C$ i zwiększ $i$ o jeden, w przeciwnym przypadku dołącz $B[j]$ do $C$ i zwiększ $j$ o jeden.
5. Powtarzaj od kroku 2 aż wszystkie wyrazy $A$ i $B$ trafią do $C.$

Scalenie wymaga $O(n+m)$ operacji porównań elementów i wstawienia ich do tablicy wynikowej.

• Zobacz przykłady implementacji tego algorytmu na stronie Wikibooks

Zastosowanie

Szczególnie jest przydatny zwłaszcza przy danych dostępnych sekwencyjnie (po kolei, jeden element naraz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego.

Złożoność czasowa

Sortowanie przez scalanie zastosowane do tablicy 7-elementowej.

Obrazek obok przedstawia drzewo rekursji wywołania algorytmu mergesort.

Mamy więc drzewo o głębokości $\log _{2}n,$ na każdym poziomie dokonujemy scalenia o łącznym koszcie $n\times c,$ gdzie $c$ jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to $n*\log _{2}n.$

Formalnie złożoność czasową sortowania przez scalanie możemy przedstawić następująco:

Bez straty ogólności załóżmy, że długość ciągu, który mamy posortować jest potęgą liczby 2:

$T(1)=O(1),$

$T(n)=2T({\tfrac {n}{2}})+O(n).$

Ciągi jednoelementowe możemy posortować w czasie stałym, czas sortowania ciągu $n$-elementowego to scalenie dwóch ciągów ${\tfrac {n}{2}}$-elementowych, czyli O(n), plus czas potrzebny na posortowanie dwóch o połowę krótszych ciągów.

Mamy:

${\begin{aligned}T(n)&=2T({\tfrac {n}{2}})+n=2(2T({\tfrac {n}{4}})+{\tfrac {n}{2}})+n\\&=2(2(2T({\tfrac {n}{8}})+{\tfrac {n}{4}})+{\tfrac {n}{2}})+n\\&=2(2(\dots 2(T({\tfrac {n}{2\cdot 2^{i}}})+{\tfrac {n}{2^{i}}})++\dots )+{\tfrac {n}{2}})+n\\&=2(2(\dots 2(T(1)+2)\dots )+{\tfrac {n}{2}})+n,\end{aligned}}$

gdzie $n=2^{k}.$

Po rozwinięciu nawiasów otrzymamy:

$T(n)=2n\log n.$

A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n) (zobacz: notacja dużego O).

Wersja nierekurencyjna

Podstawową wersję algorytmu sortowania przez scalanie można uprościć. Pomysł polega na odwróceniu procesu scalania serii. Ciąg danych możemy wstępnie podzielić na $n$ serii długości $1,$ scalić je tak, by otrzymać ${\tfrac {n}{2}}$ serii długości $2,$ scalić je otrzymując ${\tfrac {n}{4}}$ serii długości $4\dots$

Złożoność obliczeniowa jest taka sama jak w przypadku klasycznym, tu jednak nie korzystamy z rekursji, a więc zaoszczędzamy czas i pamięć potrzebną na jej obsłużenie.

Linki zewnętrzne

• Przyśpieszony MergeSort
• Algorytm przedstawiony z wykorzystaniem tańca