Sortowanie przez scalanie

Sortowanie przez scalanie

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

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

Algorytm

Wyróżnić można trzy podstawowe kroki^[1]:

1. Podział zestawu danych na dwie równe części^[4].
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^[1]:

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 ${\displaystyle A[1,\dots ,n]}$ i ${\displaystyle B[1,\dots ,m]}$ do ciągu ${\displaystyle C[1,\dots ,m+n]}$^{[potrzebny przypis]}:

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

Scalenie wymaga ${\displaystyle 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^{[potrzebny przypis]}.

Złożoność czasowa

Obrazek obok przedstawia drzewo rekursji wywołania algorytmu mergesort.

Mamy więc drzewo o głębokości ${\displaystyle \log _{2}n,}$ na każdym poziomie dokonujemy scalenia o łącznym koszcie ${\displaystyle n\times c,}$ gdzie ${\displaystyle c}$ jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to ${\displaystyle 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^[1]:

${\displaystyle T(1)=O(1),}$

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

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

Mamy:

${\displaystyle {\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 ${\displaystyle n=2^{k}.}$

Po rozwinięciu nawiasów otrzymamy:

${\displaystyle T(n)=2n\log n.}$

A więc asymptotyczny czas sortowania przez scalanie wynosi O(n log n)^[1] (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 ${\displaystyle n}$ serii długości ${\displaystyle 1,}$ scalić je tak, by otrzymać ${\displaystyle {\tfrac {n}{2}}}$ serii długości ${\displaystyle 2,}$ scalić je otrzymując ${\displaystyle {\tfrac {n}{4}}}$ serii długości ${\displaystyle 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.

Przypisy

Linki zewnętrzne

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