W zadaniu należy przeanalizować działanie danego algorytmu dla przykładowych danych.
Ponieważ w obu zadaniach dane tablice są takie same, więc przedstawiona poniżej analiza
dotyczy jednocześnie zadania 1 i 2.
Dwa pierwsze przykłady zawierają na tyle mało liczb, że działanie algorytmu można zrealizować po prostu krok po kroku, zliczając po drodze liczbę wykonanych porównań w wierszach (*) i (**). Aby rozwiązać pozostałe dwa przykłady, należy dokonać pełnej analizy algorytmu. Na początku zauważmy, że w algorytmie wartość zmiennej
x jest początkowo równa
T[1], i nigdy potem nie jest zmieniana. Dla tablicy T = [1, 2, 3, ..., 100] wartość
x będzie stale
równa 1. Zauważmy, że konstrukcja algorytmu zawiera jedną główną pętlę, a w jej środku
następujące dwie pętle:
pętla 1
wykonuj j ← j-1
(*)
dopóki T[j] > x
pętla 2
wykonuj i ← i+1
(**)
dopóki T[i] < x
W pierwszej pętli algorytm zmniejsza wskaźnik j tak długo, dopóki T[j]>x. Natomiast
w drugiej pętli algorytm zwiększa wskaźnik i tak długo, dopóki T[i]<x.
Dla tablicy T=[1, 2, 3, ..., 100], tj. dla n=100 oraz x=1, pierwsza pętla wykonuje porównania
„T[100]>x”, „T[99]>x”, ..., „T[1]>x”. Ostatnie z nich ma wartość logiczną false; wówczas
pętla kończy się, a wartość j jest równa 1. W drugiej pętli algorytm wykona tylko jedno po-
równanie, mianowicie „T[1]<x", po którym pętla zostanie przerwana. Następnie można zauważyć, że algorytm przerwie główną pętlę, gdyż nie jest prawdą, że „i<j”. Ostatecznie otrzymujemy 100 porównań wykonanych w wierszu (*) i 1 porównanie w wierszu (**). Widzimy zatem, że algorytm nie wykonał żadnej operacji zamiany.
Aby rozwiązać ostatni przykład, tj. dla T=[100,99,98...,1], zauważmy, że n=100 oraz x=100.
Zatem w pierwszej pętli algorytm wykona tylko jedno porównanie „T[100]>x”, po czym
przerwie pętlę z wartością j=100. W drugiej pętli algorytm również wykona tylko jedno porównanie „T[1]<x", po którym pętla ta zostanie przerwana z wartością i=1. Ponieważ i<j, więc algorytm wykona zamianę T[1] ↔T[100] oraz przejdzie ponownie do wykonania głównej pętli. Za drugim razem w pierwszej pętli algorytm znów wykona tylko jedno porównanie, mianowicie „T[99]<x”. W drugiej pętli natomiast zostaną wykonane porównania „T[2]<x”, „T[3]<x”, ..., „T[100]<x”, po których pętla zostanie przerwana z wartością i=100. W tym momencie zostanie przerwana również główna pętla. Oznacza to, że algorytm wykona w sumie 2 porównania w wierszu (*) i 100 w wierszu (**). Liczba zamian natomiast będzie równa 1.
Dla uzupełnienia warto jeszcze dodać, że podany algorytm tak naprawdę realizuje podział
tablicy na pewne dwie części (niekoniecznie równoliczne). W pierwszej części będą znajdowały się wszystkie liczby mniejsze od x, a w drugiej te większe lub równe x. Podobny podział
jest podstawą szybkiego algorytmu sortowania (ang. quick-sort).