Przejdź do zawartości

Sortowanie przez scalanie

Z Wikipedii, wolnej encyklopedii
Sortowanie przez scalanie
Ilustracja
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. 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 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. Eric W. Weisstein, 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

[edytuj | edytuj kod]