Sortowanie przez scalanie

Sortowanie przez scalanie (ang. merge sort) – algorytm sortowania danych, stosujący metodę dziel i zwyciężaj^[1]. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi^[2][3]. Algorytm można przedstawić w naiwnej wersji rekurencyjnej lub znacznie bardziej efektywnej wersji iteracyjnej.

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 w wersji rekurencyjnej

Wersja nierekurencyjna

Algorytm iteracyjny jest bardzo prosty. W pierwszej iteracji scalamy pojedyncze elementy ciągu w posortowane pary, w drugiej posortowane pary scalamy w posortowane czwórki, następnie czwórki scalamy w posortowane ósemki, i tak dalej, aż w ostatnim przebiegu scalimy dwie posortowane połówki ciągu w posortowaną całość.

Dla ciągu o długości ${\displaystyle n}$ każdy przebieg scalający wymaga ${\displaystyle n}$ operacji, a liczba przebiegów to ${\displaystyle \log _{2}n,}$ gdyż pierwszy przebieg tworzy posortowane pary, a każdy następny podwaja długość posortowanych podciągów.

W pseudokodzie algorytm można zapisać następująco^[1]:

SCALAJ_SORT(T)
    n ← długość T
    rozmiar ← 1
    DOPÓKI rozmiar < n :
        DLA i ← 0 DO n - 1 KROK 2 * rozmiar :
            lewy_pocz ← i
            lewy_koniec ← min(i + rozmiar - 1, n - 1)
            prawy_pocz ← lewy_koniec + 1
            prawy_koniec ← min(i + 2 * rozmiar - 1, n - 1)
            JEŚLI prawy_pocz < n :
                SCALAJ(T, lewy_pocz, lewy_koniec, prawy_koniec)
        rozmiar ← 2 * rozmiar

Procedura scalania dwóch ciągów może być przedstawiona w postaci pseudokodu:

SCALAJ(T, lewy_pocz, lewy_koniec, prawy_koniec)
    L ← T[lewy_pocz : lewy_koniec]  ⬅ (Kopia lewej połowy)
    P ← T[prawy_pocz : prawy_koniec] ⬅ (Kopia prawej połowy)
    i ← 0, j ← 0, k ← lewy_pocz
    DOPÓKI i < długość L ORAZ j < długość P :
        JEŚLI L[i] ≤ P[j] :
            T[k] ← L[i]
            i ← i + 1
        W PRZECIWNYM RAZIE :
            T[k] ← P[j]
            j ← j + 1
        k ← k + 1
    DOPÓKI i < długość L :
        T[k] ← L[i]
        i ← i + 1
        k ← k + 1
    DOPÓKI j < długość P :
        T[k] ← P[j]
        j ← j + 1
        k ← k + 1

Łatwo pokazać, że złożoność scalania jest proporcjonalna do długości wynikowego ciągu: pierwsza pętla wykonuje się dopóki indeksy i oraz j leżą w zakresie lewej i prawej połówki (innymi słowy - dopóki jest co porównywać). Kiedy jeden ze scalanych ciągów się wyczerpie, algorytm przechodzi do drugiej lub trzeciej pętli, które kopiują do T "resztki". Należy zwrócić uwagę, że zawsze wykona się albo druga albo trzecia pętla, zależnie od tego, czy w pierwszej wyczerpał się ciąg P, czy L.

Dużą zaletą algorytmu jest jego stabilność, co w przypadku sortowania oznacza zachowywanie w wynikowym ciągu kolejności równych danych. Jest to osiągane dzięki zastosowaniu nieostrej nierówności w warunku instrukcji JEŻELI w szóstej linii scalania.

Algorytm rekurencyjny

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

1. Podział zestawu danych na dwie równe części^[4]. Należy zwrócić uwagę, że w przypadku sortowania wektora (tablicy jednowymiarowej) podział nie ma sensu, bo wektor jest ze swej istoty "podzielony" - dostęp do każdego z jego elementów ma taki sam koszt.
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]}.

Sortowanie przez scalanie jest też stosowane do sortowania złożonych obiektów, które można porządkować według różnych kryteriów. Wtedy stabilność (pozostawianie kolejności elementów równych) powoduje, że sortowanie elementów posortowanych wcześniej według innego kryterium nie psuje wcześniejszych wyników. Wyobraźmy sobie na przykład sortowanie wyników egzaminu (obiektów składających się z imienia, nazwiska i oceny) najpierw alfabetycznie, a następne według ocen. Użycie sortowania przez scalanie pozwala uzyskać listę, w której grupy z równymi ocenami pozostaną posortowane alfabetycznie. Z tego względu sortowanie przez scalanie jest użyte na przykład w standardowej bibliotece Javy do sortowania obiektów.

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 ${\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).

Przypisy

1. Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest: Wprowadzenie do algorytmów. Warszawa: Wydawnictwa Naukowo-Techniczne, 1997, 1998, s. 32–35. ISBN 83-204-2317-1.
2. DonaldD. Knuth DonaldD., The Art of Computer Programming 3, Sorting and Searching (2nd ed.), Addison-Wesley, s. 158–168, ISBN 0-201-89685-0.
3. Eric W.E.W. Weisstein Eric W.E.W., Opis działania algorytmu, [w:] MathWorld, Wolfram Research [dostęp 2016-10-16] (ang.).
4. W przypadku nieparzystej liczby wyrazów jedna część będzie o jeden wyraz dłuższa.

Linki zewnętrzne

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