Sortowanie przez scalanie

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania
Sortowanie przez scalanie w wersji rekurencyjnej

W informatyce sortowanie przez scalanie (ang. merge sort), to rekurencyjny algorytm sortowania danych, stosujący metodę dziel i zwyciężaj[1]. Odkrycie algorytmu przypisuje się Johnowi von Neumannowi[potrzebne źródło].

Algorytm[edytuj | edytuj kod]

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

  1. Podziel zestaw danych na dwie równe części[2]
  2. Zastosuj sortowanie przez scalanie dla każdej z nich oddzielnie, chyba że pozostał już tylko jeden element;
  3. Połącz posortowane podciągi w jeden.

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 A[1..n] i B[1..m] do ciągu C[1..m+n][potrzebne źródło]:

  1. Utwórz wskaźniki na początki ciągów A i Bi=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]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.

Zastosowanie[edytuj | edytuj kod]

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

Złożoność czasowa[edytuj | edytuj kod]

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 log2 n, na każdym poziomie dokonujemy scalenia o łącznym koszcie n×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 log2 n×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].

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{array}{cl}
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(...2(T(\tfrac{n}{2\cdot 2^i})+\tfrac{n}{2^i})++...)+\tfrac{n}{2})+n \\ \\
     & = 2(2(...2(T(1)+2)...)+\tfrac{n}{2})+n
\end{array}

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)[1] (zobacz: notacja dużego O).

Wersja nierekurencyjna[edytuj | edytuj kod]

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...

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[edytuj | edytuj kod]

  1. 1,0 1,1 1,2 1,3 1,4 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. w przypadku nieparzystej liczby wyrazów jedna część będzie o 1 wyraz dłuższa

Linki zewnętrzne[edytuj | edytuj kod]