If you're seeing this message, it means we're having trouble loading external resources on our website.

Jeżeli jesteś za filtrem sieci web, prosimy, upewnij się, że domeny *.kastatic.org i *.kasandbox.org są odblokowane.

Główna zawartość

Łą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 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 Θ(n). Rzeczywiście, zobaczymy w jaki sposób scalić n elementów w czasie Θ(n).
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 qp+1 elementów. A co z tablicą highHalf? Podtablica array[q+1..r] zawiera rq 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] (zatemp=0, q=3 oraz r=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:
  • i
    • oznacza indeks następnego elementu tablicy lowHalf, którego jeszcze nie skopiowaliśmy do tablicy array. Początkowo, i równa się 0.
  • j
    • oznacza indeks następnego elementu tablicy highHalf, którego jeszcze nie skopiowaliśmy do tablicy array. Początkowo j równa się 0.
  • k
    • oznacza indeks następnego elementu w tablicy array, do którego będziemy kopiować kolejny element. Początkowo k równa się p.
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 elementów zajmuje Θ(n) 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:
  1. Skopiuj każdy element z tablicy array[p..r] albo do tablicy lowHalf, albo to tablicy highHalf.
  2. Tak długo jak istnieją elementy nie skopiowane w obu tablicach:lowHalf oraz highHalf, porównuj ze sobą dwa pierwsze nie skopiowane elementy tablic i kopiuj mniejszy z nich do tablicy array.
  3. Kiedy już jedna z tablic lowHalf lub highHalf ma skopiowane elementy do tablicy array, skopiuj wszystkie pozostałe nie skopiowane jeszcze elementy z tej drugiej tymczasowej tablicy do tablicy array.
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 elementów, jest scalana rzeczywiście w czasie Θ(n).
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.

Chcesz dołączyć do dyskusji?

Na razie brak głosów w dyskusji
Rozumiesz angielski? Kliknij tutaj, aby zobaczyć więcej dyskusji na angielskiej wersji strony Khan Academy.