Rozważmy następujący problem. Na początku semestru dziekanat pewnej Uczelni przygotował alfabetycznie uporządkowane listy studentów każdej z grup drugiego roku. Na koniec semestru potrzebny jest jednak protokół egzaminacyjny zawierający nazwiska wszystkich studentów drugiego roku. Jak stworzyć nową, alfabetycznie uporządkowaną listę, tak by nikogo nie pominąć i wykonać jak najmniej pracy?

Sformalizowana wersja tego problemu, to problem scalania:

Dane są dwa ciągi uporządkowane a[1],..., a[n] oraz b[1],..., b[n]. Zbudować ciąg uporządkowany o n+m elementach e[1], ..., e[n+m], złożony z wszystkich elementów obu ciągów. 

Przykład 4.1

(a) Niech ciąg a składa się ze słów  bit, kit, lit, mit, wit, a ciąg b ze słów   kok, lok, rok, sok, tok. W wyniku operacji scalania otrzymamy ciąg   bit,  kit, kok, lit, lok, mit, rok, sok, tok, wit.

(b) Jeżeli a = (2,5,6,8,9), b = (0,1,3,4,7), to w wyniku scalania otrzymamy ciąg e = (0,1,2,3,4,5,6,7,8,9).J

Specyfikacja algorytmu:

wp = { a[1] £ ...£ a[n],  b[1]£ ...£ b[m]}

wk = {e[1] £ e[2] £... £ e[n+m], ciąg e jest permutacją elementów a[1],...,a[n], b[1],...,b[m]}

Każdy algorytm, całkowicie poprawny ze względu na tę specyfikację będziemy uznawali za rozwiązanie problemu scalania.
 

Idea rozwiązania:

Wyobraźmy sobie bramkę, przed którą stoją dwie uporządkowane kolejki (tzn. ciąg a i ciąg b). W każdym kroku, przez bramkę przechodzi jeden element: mniejszy z tych, które znajdują się aktualnie na początku kolejek.  Jego kolejka przesuwa się tym samym o jedną pozycję do przodu. Większy pozostaje przed bramką tak długo, aż na początku drugiej kolejki pojawi się element od niego większy, lub druga kolejka będzie pusta.  

Przykład 4.2

Niech ciągi a i b zawierają odpowiednio liczby 2,3,5,6,8,9 oraz 0,1,4,7. W kolejnych wierszach poniższej tabeli zapisano kolejne kroki algorytmu scalania. Kolorem czerwonym zaznaczono elementy porównywane w danym kroku. Element mniejszy z porównywanych jest w zapisany w ciągu wynikowym.

W chwili, gdy porównaliśmy 8 i 7,  i siódemka została zapisana w ciągu wynikowym, elementy 8,9 z pierwszego ciągu możemy, bez wykonywania porównań, dopisać na końcu ciągu wynikowego. J

Algorytm

Niech a będzie ciągiem o długości n, a b ciągiem o długości m. W opisanym poniżej algorytmie Merge,  oba ciągi wejściowe a i  b zostały rozszerzone o jeden element, oznaczony tutaj + ¥. Zakładamy, że jest on większy od wszystkich innych elementów obu ciągów. Taki zabieg pozwoli nam uprościć nieco strukturę algorytmu. Zadbamy jednak o to, by ciąg e otrzymany w wyniku  miał dokładnie n+m elementów.

Poprawność algorytmu

Zauważmy, że elementy dodatkowe, dopisane do ciągów a i b, nie mogą się znaleźć w ciągu wynikowym, gdyż pętla jest wykonywana tylko  (n+m) razy. Gdyby, w którymś momencie i= n+1, tzn. a[i] =+ ¥ , to przy porównywaniu tego elementu z b[j] dla j<n+1, wygra b[j] i to b[j] zostanie zapisane w ciągu wynikowym. Analogicznie w przypadku, gdy j=m+1. Jeśli zaś oba wskaźniki i, j wskazują element specjalny, to znaczy, że wszystkie poprzednie elementy już zostały wpisane do tablicy wynikowej, a więc k musi być w tym momencie równe n+m+1. Warunek pętli "while" nie będzie spełniony i zakończymy wykonywanie algorytmu.

Jest oczywiste, że algorytm zatrzymuje się dla dowolnych danych, gdyż zmienna kontrolująca pętlę zmienia się od 1 do n+m. Trzeba jeszcze pokazać, że otrzymany wynik jest ciągiem uporządkowanym złożonym z elementów danych ciągów.

Przed pierwszym wejściem do pętli "while" jest trywialnie spełniony warunek  e[1] £ e[2] £... £ e[k-1]. Załóżmy, że rozpoczynamy pewną iterację pętli "while" i spełnione są własności (*):

 e[1] £ e[2] £... £ e[k-1], i £ n+1, j £ m+1, k = (i + j -1), k £ (n+m+1),  (*)

(ciąg e[1],...,e[k-1] jest  permutacją ciągu a[1],...,a[i-1],b[1],...,b[j-1] ).

Formuły te mówią, że k-1 elementów w ciągu e tworzy ciąg uporządkowany, a ponadto  i-1 elementów ciągu a oraz  j-1 elementów ciągu b zostało już zapisanych na pozycjach od 1 do k-1 ciągu e.

Po wykonaniu instrukcji warunkowej "if  (a[i] £ b[j])..." , na miejscu k-tym w ciągu e pojawi się  mniejszy z elementów a[i], b[j] oraz, albo i, albo j wzrośnie o jeden.  Ponieważ ciągi a i b są uporządkowane niemalejąco zatem wstawiony element e[k] jest niemniejszy od wszystkich  elementów, które znajdują się na wcześniejszych pozycjach w ciągu e. Mamy więc w tablicy e aż k elementów uporządkowanych, oraz   i+j-1 = k+1.

e[1]  £... £ e[k-1] £ e[k], i £ n+1, j £ m+1, (k+1) = (i + j -1),  k £ (n+m+1),

(ciąg e[1],...,e[k] jest  permutacją elementów ciągu a[1],...,a[i-1],b[1],...,b[j-1] ).

Po wykonaniu instrukcji przypisania "k:=k+1;" ponownie spełnione są własności (*). Wykazaliśmy tym samym, że jest to niezmiennik pętli. Z twierdzenia o niezmienniku (por. wykład I, p.3), ta sama formuła jest spełniona w chwili wyjścia z pętli. Wtedy jednak k = n+m+1 i wszystkie elementy, zarówno ciągu a, jak i b, znalazły się już w ciągu e oraz  e[1]  £... £ e[n+m]. Spełniony jest zatem warunek końcowy specyfikacji.

Koszt algorytmu

Ponieważ w pętli "while" wykonujemy w każdej iteracji tylko jedno porównanie, a liczba iteracji wynosi dokładnie n+m, zatem koszt algorytmu  jest liniowy w stosunku do długości ciągów scalanych i wynosi

T(n) = Q(n+m).

Pytanie 4: Ile porównań elementów musi wykonać algorytm Merge, jeżeli wiadomo, że  a[n]<b[1]? (Nie liczymy porównań z elementem specjalnym + ¥.)

« poprzedni punkt

następny punkt »