Sortowanie przez scalanie polega na podzieleniu sortowanej struktury danych na dwie części, następnie na rekurencyjnymrekurencjarekurencyjnym sortowaniu każdej z tych części i ponownym scaleniu już posortowanych części w jedną całość. Warto wiedzieć, że jako pierwszy tę metodę opisał John von NeumannJohn von NeumannJohn von Neumann, znany jako twórca m.in. teorii gier oraz koncepcji automatów komórkowychkoncepcja automatów komórkowychkoncepcji automatów komórkowych. Algorytm sortowania przez scalanie oparty jest na metodzie dziel i zwyciężajdziel i zwyciężajdziel i zwyciężaj.

Scalanie posortowanych tablic

Wyobraźmy sobie, że mamy dwie półki, każda z losową liczbą książek. Książki na półkach ułożone są w kolejności alfabetycznej. Naszym celem jest ułożenie wszystkich książek na trzeciej półce, w kolejności alfabetycznej. By to zrobić, porównujemy ze sobą pierwszą książkę z półki nr 1 z pierwszą książką na półce nr 2. Książka z literą położoną wcześniej w alfabecie, zostaje przeniesiona na trzecią półkę. Czynność powtarzamy, porównując książki, które ułożone są jako pierwsze na półkach. W momencie, gdy skończą nam się książki na jednej z półek, resztę książek z drugiej półki po prostu przenosimy na koniec naszej trzeciej, dodatkowej półki. Aby lepiej zrozumieć algorytm scalania książek na półkach, przeanalizuj rysunek.

R698jHQlBcgzd
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Etapy sortowania przez scalanie

Chcemy uporządkować niemalejąco n-elementową tablicę liczb całkowitych. W jaki sposób to zrobić, korzystając z metody sortowania przez scalanie?

Aby użyć omówionego wcześniej algorytmu scalania, musimy podzielić tablicę na mniejsze, same w sobie posortowane tablice. W tym celu tablicę dzielimy na pół – jeżeli liczba elementów jest nieparzysta, pierwsza tablica będzie miała jeden element więcej.

Proces powtarzamy do momentu, w którym osiągniemy tablice jednoelementowe.  Wiemy, że tablica posiadająca jeden element już jest posortowana. Dzięki temu możemy scalić dwie tablice jednoelementowe i uzyskać kolejną, posortowaną dwuelementową tablice. Następnie możemy scalić dwie posortowane tablice dwuelementowe, aby uzyskać czteroelementową itd. Przejdźmy do rysunku przedstawiającego kolejne etapy sortowania przez scalanie na podstawie przykładowej tablicy.

RFhg88Lnkk3gn
Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Pseudokod sortowania przez scalanie

Specyfikacja:

Dane:

  • n – liczba naturalna dodatnia, liczba elementów tablicy

  • tablica – n‑elementowa tablica liczb całkowitych

Wynik:

  • posortowana niemalejąco tablica całkowitych liczb tablica

Algorytm ten można zapisać za pomocą pseudokodu w następujący sposób:

Linia 1. funkcja Sortowanie podkreślnik scalanie otwórz nawias okrągły tablica przecinek pocz przecinek kon zamknij nawias okrągły. Linia 2. jeżeli pocz otwórz nawias ostrokątny kon. Linia 3. połowa ← zaokrąglij w dół do całkowitej otwórz nawias okrągły otwórz nawias okrągły pocz plus kon zamknij nawias okrągły prawy ukośnik 2 zamknij nawias okrągły. Linia 4. Sortowanie podkreślnik scalanie otwórz nawias okrągły tablica przecinek pocz przecinek połowa zamknij nawias okrągły. Linia 5. Sortowanie podkreślnik scalanie otwórz nawias okrągły tablica przecinek połowa plus 1 przecinek kon zamknij nawias okrągły. Linia 6. Scal otwórz nawias okrągły tablica przecinek pocz przecinek połowa przecinek kon zamknij nawias okrągły. Linia 8. funkcja Scal otwórz nawias okrągły tablica przecinek pocz przecinek polowa przecinek kon zamknij nawias okrągły. Linia 9. n1 ← polowa minus pocz plus 1. Linia 10. n2 ← kon minus polowa. Linia 12. utwórz tablicę L o rozmiarze n1. Linia 13. utwórz tablicę R o rozmiarze n2. Linia 15. dla i od 0 do n1 minus 1. Linia 16. L otwórz nawias kwadratowy i zamknij nawias kwadratowy ← tablica otwórz nawias kwadratowy pocz plus i zamknij nawias kwadratowy. Linia 18. dla j od 0 do n2 minus 1. Linia 19. R otwórz nawias kwadratowy j zamknij nawias kwadratowy ← tablica otwórz nawias kwadratowy polowa plus 1 plus j zamknij nawias kwadratowy. Linia 21. i ← 0. Linia 22. j ← 0. Linia 23. k ← pocz. Linia 25. dopóki i otwórz nawias ostrokątny n1 ORAZ j otwórz nawias ostrokątny n2. Linia 26. jeżeli L otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias ostrokątny znak równości R otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 27. tablica otwórz nawias kwadratowy k zamknij nawias kwadratowy ← L otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 28. i ← i plus 1. Linia 29. w przeciwnym razie. Linia 30. tablica otwórz nawias kwadratowy k zamknij nawias kwadratowy ← R otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 31. j ← j plus 1. Linia 32. k ← k plus 1. Linia 34. dopóki i otwórz nawias ostrokątny n1. Linia 35. tablica otwórz nawias kwadratowy k zamknij nawias kwadratowy ← L otwórz nawias kwadratowy i zamknij nawias kwadratowy. Linia 36. i ← i plus 1. Linia 37. k ← k plus 1. Linia 39. dopóki j otwórz nawias ostrokątny n2. Linia 40. tablica otwórz nawias kwadratowy k zamknij nawias kwadratowy ← R otwórz nawias kwadratowy j zamknij nawias kwadratowy. Linia 41. j ← j plus 1. Linia 42. k ← k plus 1.

W jaki sposób zastosowane jest podejście „dziel i zwyciężaj”dziel i zwyciężaj„dziel i zwyciężaj” w zapisanym pseudokodzie?

Przeanalizujmy wspólnie instrukcję tego algorytmu. Na początek sprawdzamy, czy podana tablica zawiera więcej niż jeden element. Jeżeli odpowiedź brzmi tak, przechodzimy do kolejnych poleceń.

Linijka jeżeli pocz < kon jest odpowiedzialna za sprawdzenie, czy w tablicy znajduje się więcej niż jeden element. Dla przykładowych wartości pocz = 1, kon = 2 warunek jest spełniony – tablica ma dwa elementy, element 1 oraz element 2. Jeżeli jednak pocz = 2, kon = 2, wtedy tablica ma tylko jeden element.

Od tego kroku zostaje wykorzystana strategia „dziel i zwyciężaj”.  Przyjrzyj się i spróbuj zauważyć podobieństwo opisu tej strategii z zapisanym wcześniej za pomocą pseudokodu algorytmem sortowania.

  • Do zmiennej połowa zapisywany jest indeks podziału tablicy. Pamiętajmy, żeby wynik zaokrąglić w dół do części całkowitej. Dzięki temu tablica będzie podzielona na dwie części. W przypadku parzystej liczby elementów, będą to dwie równe części, w wypadku nieparzystej – pierwsza część będzie zawierała o jeden element więcej od drugiej.

  • Następnie rekurencyjnie wywołujemy funkcję sortowania przez scalanie, osobno dla każdej z dwóch części. Tablica dzielona jest aż do otrzymania tablic jednoelementowych, czyli aż do momentu, w którym algorytm znajdzie przypadek podstawowyprzypadek podstawowyprzypadek podstawowy.

  • Ostatnia instrukcja pseudokodu wywołuje funkcję, która łączy posortowane fragmenty tablic w jedną posortowaną tablicę.

Złożoność czasowa i pamięciowa algorytmu

Tablica dzielona jest zawsze na dwie części (co mogliśmy zaobserwować na rysunku przedstawiającym kolejne etapy sortowania przez scalanie tablicy liczb). W wypadku parzystej liczby elementów są to zawsze dwie równe części. W przypadku nieparzystej liczby elementów pierwsza część zawiera tylko o jeden element więcej od drugiej. Zatem dla n‑elementowej tablicy, mamy log2n poziomów zagnieżdżenia funkcji. Złożoność operacji scalania na każdym poziomie drzewa niezależnie od uporządkowania elementów wynosi nc, gdzie c jest stałą zależną od jakości używanego sprzętu. A więc czas działania algorytmu zarówno dla zbiorów posortowanych, posortowanych odwrotnie jak i nieposortowanych jest proporcjonalny do:

n·log2n

Zatem złożoność czasowazłożoność czasowazłożoność czasowa wynosi:

O(n·log2n)

Sortowanie przez scalanie wymaga użycia dodatkowej tablicy, w której będziemy zachowywać wynik scalania, więc dla n‑elementowej tablicy złożoność pamięciowa wynosi O(n). W związku z tym, merge sort nie jest tzw. sortowaniem w miejscusortowanie w miejscusortowaniem w miejscu.

Słownik

dziel i zwyciężaj
dziel i zwyciężaj

metoda, która polega na podzieleniu problemu na mniejsze, podobne problemy, znalezieniu ich rozwiązań, a następnie ponownym połączeniu ich w jedną całość, by otrzymać rozwiązanie całego problemu

John von Neumann
John von Neumann

węgierski matematyk, chemik, fizyk i informatyk; jest uznawany za głównego twórcę teorii gier i formalizmu matematycznego mechaniki kwantowej

przypadek podstawowy
przypadek podstawowy

przypadek, dla którego funkcja rekurencyjna nie wywołuje samej siebie, a zamiast tego zwraca z góry określoną wartość

rekurencja
rekurencja

sytuacja, w której funkcja wywołuje samą siebie, aż do napotkania przypadku podstawowego

sortowanie w miejscu
sortowanie w miejscu

tzw. in situ; algorytm, który do posortowania zbioru danych potrzebuje stałej ilości pamięci komputera, niezależnej od rozmiaru danych wejściowych; wszelkie potrzebne do otrzymania wyniku obliczenia są wykonywane w pamięci, w której znajdują się dane

złożoność czasowa
złożoność czasowa

cecha algorytmu, która wyraża czas niezbędny do wykonania danego algorytmu dla konkretnych danych, podana jako funkcja rozmiaru tych danych wejściowych; zazwyczaj rozpatruje się liczbę operacji podstawowych (dominujących), w przypadku sortowania najczęściej jest to operacja porównania wartości dwóch elementów, można też przyjąć operację przestawiania elementów

koncepcja automatów komórkowych
koncepcja automatów komórkowych

polega na zastąpieniu zbioru skomplikowanych równań opisujących zachowanie się wielu układów fizycznych, systemem komórek sąsiadujących ze sobą według pewnego ustalonego wzorca