Sortowanie przez scalanie

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Sortowanie przez scalanie
Merge sort animation2.gif
Przykład działania
Rodzaj Sortowanie
Struktura danych Tablica, lista
Złożoność
Czasowa
Pamięciowa
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].

Algorytm[edytuj | edytuj kod]

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

  1. Podziel zestaw danych na dwie równe części[4].
  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 ciąg posortowany.

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 i do ciągu [potrzebny przypis]:

  1. Utwórz wskaźniki na początki ciągów i
  2. Jeżeli ciąg wyczerpany dołącz pozostałe elementy ciągu do i zakończ pracę.
  3. Jeżeli ciąg wyczerpany dołącz pozostałe elementy ciągu do i zakończ pracę.
  4. Jeżeli dołącz do i zwiększ o jeden, w przeciwnym przypadku dołącz do i zwiększ o jeden.
  5. Powtarzaj od kroku 2 aż wszystkie wyrazy i trafią do

Scalenie wymaga 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 naraz), na przykład w postaci listy jednokierunkowej (tj. łączonej jednostronnie) albo pliku sekwencyjnego[potrzebny przypis].

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 na każdym poziomie dokonujemy scalenia o łącznym koszcie gdzie jest stałą zależną od komputera. A więc intuicyjnie, tzn. nieformalnie możemy dowieść, że złożoność algorytmu mergesort to

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

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

Mamy:

gdzie

Po rozwinięciu nawiasów otrzymamy:

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 serii długości scalić je tak, by otrzymać serii długości scalić je otrzymując serii długości

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. 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. Donald Knuth, The Art of Computer Programming 3, Sorting and Searching (2nd ed.), Addison-Wesley, s. 158–168, ISBN 0-201-89685-0.
  3. Opis działania algorytmu (ang.). mathworld.wolfram.com. [dostęp 2016-10-16].
  4. W przypadku nieparzystej liczby wyrazów jedna część będzie o 1 wyraz dłuższa.

Linki zewnętrzne[edytuj | edytuj kod]