Sortowanie przez scalanie


Sortowanie przez scalanie w encyklopedii

Z Wikipedii, wolnej encyklopedii Przejdź do nawigacji Przejdź do wyszukiwania Sortowanie przez scalanie w wersji rekurencyjnej

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

Spis treści

Algorytm | edytuj kod

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

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

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

Zastosowanie | edytuj kod

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 | 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 log 2 n , {\displaystyle \log _{2}n,} na każdym poziomie dokonujemy scalenia o łącznym koszcie n × c , {\displaystyle n\times c,} gdzie c {\displaystyle 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 . {\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]:

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

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

Mamy:

T ( n ) = 2 T ( n 2 ) + n = 2 ( 2 T ( n 4 ) + n 2 ) + n = 2 ( 2 ( 2 T ( n 8 ) + n 4 ) + n 2 ) + n = 2 ( 2 ( 2 ( T ( n 2 2 i ) + n 2 i ) + + ) + n 2 ) + n = 2 ( 2 ( 2 ( T ( 1 ) + 2 ) ) + n 2 ) + n , {\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 n = 2 k . {\displaystyle n=2^{k}.}

Po rozwinięciu nawiasów otrzymamy:

T ( n ) = 2 n log n . {\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 | 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 {\displaystyle n} serii długości 1 , {\displaystyle 1,} scalić je tak, by otrzymać n 2 {\displaystyle {\tfrac {n}{2}}} serii długości 2 , {\displaystyle 2,} scalić je otrzymując n 4 {\displaystyle {\tfrac {n}{4}}} serii długości 4 {\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 | edytuj kod

  1. a b c d e 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 [online], 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 | edytuj kod

Na podstawie artykułu: "Sortowanie przez scalanie" pochodzącego z Wikipedii
OryginałEdytujHistoria i autorzy