Łączenie w liniowym czasie

Wciąż jeszcze pozostał nam ten kawałek algorytmu przez scalanie, jakim jest funkcja scalanie, która scala dwie przyległe posortowane potablice array[p..q] oraz array[q+1..r] w jedną posortowaną podtablicę array[p..r]. Zobaczymy jak skonstruować tą funkcję, aby było to jak najbardziej efektywne. Powiedzmy, że te dwie podtablice mają w sumie $n$n elementów. Musimy zbadać każdy z tych elementów, aby je scalić ze sobą, więc najlepszy czas scalania, jaki mamy nadzieję osiągnąć to $\Theta(n)$\Theta, left parenthesis, n, right parenthesis. Rzeczywiście, zobaczymy w jaki sposób scalić $n$n elementów w czasie $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Aby scalić posortowane podtablice array[p..q] oraz array[q+1..r], a rezultat otrzymać w podtablicy array[p..r], musimy najpierw stworzyć tablice tymczasowe i skopiować potablice array[p..q] oraz array[q+1..r] do tych tymczasowych tablic. Nie możemy bowiem nadpisywać elementów podtablicy array[p..r] dopóki bezpiecznie nie skopiujemy elementów z podtablic array[p..q] oraz array[q+1..r].

Zatem pierwszą czynnością funkcji scalanie będzie stworzenie dwóch tymczasowych tablic, lowHalf oraz highHalf, do których skopiujemy wszystkie elementy: z podtablicy array[p..q] do tablicy lowHalf, a z podtablicy array[q+1..r] do tablicy highHalf. Jak duża powinna być tablica lowHalf? Podtablica array[p..q] zawiera $q-p+1$q, minus, p, plus, 1 elementów. A co z tablicą highHalf? Podtablica array[q+1..r] zawiera $r-q$r, minus, q elementów. (W języku JavaScript nie musimy nadawać tablicom konkretnych rozmiarów, gdy je tworzymy, jednak trzeba to robić w wielu innych językach programowania i dlatego rozważamy to przy opisywaniu tego algorytmu.)

W naszym przykładzie tablica array [14, 7, 3, 12, 9, 11, 6, 2], wygląda następująco, po sortowaniu rekurencyjnym: array[0..3] oraz array[4.{,}7] (zatem$p=0$p, equals, 0, $q=3$q, equals, 3 oraz $r=7$r, equals, 7). Te podtablice kopiujemy do lowHalf i highHalf:

Liczby w tablicy array są zapisane szarym kolorem, aby pokazać, że pomimo tego, iż te pozycje tablicy zawierają jakieś liczby, "prawdziwe" liczby są teraz w tablicach lowHalf oraz highHalf. Możemy teraz nadpisać liczby zapisane szarym kolorem.

Następnie scalamy dwie posortowane tablice znajdujące się w lowHalf i highHalf, z powrotem w tablicę array[p..r]. Najmniejszą wartość, jaka znajduje się w tych dwóch podtablicach powinniśmy umieścić w miejscu array[p]. Gdzie może znajdować się ta najmniejsza wartość? Ponieważ podtablice są posortowane, najmniejsza wartość musi znajdować się w jednym z dwóch miejsc: albo lowHalf[0] czy highHalf[0]. (Istnieje taka możliwość, że taka sama wartość znajduje się w obu tych miejscach, wtedy wybieramy jedną z nich.) Wykorzystując tylko jedno porównanie, możemy określić czy kopiować lowHalf[0] czy highHalf[0] do array[p]. W naszym przykładzie, highHalf[0] jest mniejsze. Ustalmy również trzy zmienne, odwołujące się do indeksów tych tablic:

Gdy już skopiujemy wartość z tablicy lowHalf lub tablicy highHalf do tablicy array, musimy zwiększyć o 1 zmienną k, abyśmy mogli skopiować następny najmniejszy element do kolejnej pozycji tablicy array. Musimy również zwiększyć o 1 zmienną i jeśli kopiowaliśmy element z tablicy lowHalf lub zmienną j jeśli kopiowaliśmy element z tablicy highHalf. Tak oto wyglądają tablice przed i po skopiowaniu pierwszego elementu to tablicy array:

Teraz zaznaczyliśmy szarym kolorem element highHalf[0], aby wskazać, że nie zawiera on już elementu, który będziemy brać pod uwagę. Niescalona część tablicy highHalf rozpoczyna się od indeksu j, który teraz wynosi 1. Wartość elementu array[p] nie jest już zaznaczona kolorem szarym, ponieważ skopiowaliśmy w to miejsce "prawdziwą" wartość.

Gdzie teraz znajduje się następna wartość, którą należy skopiować do array? Jest to albo pierwszy nie skopiowany jeszcze element z tablicy lowHalf (lowHalf[0]) albo pierwszy nie skopiowany jeszcze element z tablicy highHalf (highHalf[1]). Stosując tylko jedno porównanie stwierdzamy, że lowHalf[0] ma mniejszą wartość, więc kopiujemy ją do array[k] oraz zwiększamy o 1 zmienną k i zmienną i:

Następnie porównujemy lowHalf[1] oraz highHalf[1], określając, że powinniśmy skopiować wartość z highHalf[1] do array[k]. Następnie zwiększamy o 1 zmienną k oraz zmienną j:

Kontynuujemy to postępowanie zawsze porównując ze sobą lowHalf[i] oraz highHalf[j], kopiując mniejszą z tych dwóch wartości do array[k] oraz zwiększając o jeden zmienną i lub zmienną j:

W końcu wszystkie elementy z jednej z tablic: lowHalf lub highHalf są skopiowane to tablicy array. W naszym przykładzie wszystkie elementy z tablicy highHalf są skopiowane wcześniej niż ostatnich kilka elementów tablicy lowHalf. Kończymy scalanie poprzez proste kopiowanie pozostałych - jeszcze nie skopiowanych - elementów z tablicy lowHalf lub z tablicy highHalf:

Twierdziliśmy na początku, że scalanie $n$n elementów zajmuje $\Theta(n)$\Theta, left parenthesis, n, right parenthesis czasu i dlatego czas wykonania scalania jest liniowo zależny od rozmiaru podtablicy. Zobaczmy dlaczego to stwierdzenie jest prawdziwe. Widzieliśmy trzy części, z jakich składa się scalanie:

Jak wiele linii kodu potrzebujemy, aby wykonać każdy z tych kroków? Jest to liczba stała na jeden element. Każdy element jest kopiowany z tablicy array albo do tablicy lowHalf, albo do tablicy highHalf dokładnie jeden raz w kroku 1. Każde porównanie w kroku 2 zajmuje stałą ilość czasu, ponieważ porównuje po prostu dwa elementy, a każdy z nich "wygrywa" porównanie co najwyżej jeden raz. Każdy element jest kopiowany do tablicy array dokładnie jeden raz w kroku 2 lub 3. Gdy już wykazaliśmy, że każda linia kodu to stała wartość czasu wykonania na jeden element, możemy podsumować, że podtablica array[p..q] zawierająca $n$n elementów, jest scalana rzeczywiście w czasie $\Theta(n)$\Theta, left parenthesis, n, right parenthesis.

Twoje następne zadanie polegać będzie na zastosowaniu scalania opisanego w tym rozdziale. Łącząc te dwa algorytmy implementujesz pełny algorytm sortowania przez scalanie.

Materiał powstał we współpracy profesorów z Dartmouth Computer Science Thomasa Cormena i Devina Balkcoma oraz zespołu nauczycieli informatyki Khan Academy. Materiał jest udostępniony na licencji CC-BY-NC-SA.