23
5. Podstawowe algorytmy i ich cechy.
5.1. Wyszukiwanie liniowe i binarne
5.1.1. Wyszukiwanie liniowe
Wyszukiwanie jest jedną z najczęściej wykonywanych
operacji na strukturach danych i dotyczy wszystkich,
omawianych w trakcie wykładu, struktur danych.
Wyszukując możemy mieć różne cele. Możemy szukać:
elementów posiadających określone cechy (w szczególności -
elementów najmniejszych, lub największych). Możemy też
zadowolić się tylko stwierdzeniem, czy element o określonych
cechach występuje w strukturze, czy też nie.
Przedstawiony na rys. 11 przykładowy algorytm zwraca
indeks tego elementu tablicy, którego wartość po raz pierwszy
równa się zadanej wartości x. Wyszukiwanie odbywa się w
jednowymiarowej tablicy danych typu całkowitego,
zadeklarowanej według (1) [str. 7]. W przypadku nie
stwierdzenia wystąpień elementów o wartościach równych
zadanej wartości x, algorytm zwraca sygnał o nieistnieniu
takich elementów.
Jest to przykład tzw. wyszukiwania liniowego. Jego cechą
charakterystyczną jest konieczność przeglądania, w sytuacji
najgorszego przypadku, całej struktury danych. W dalszej
części wykładu przedstawione zostanie wyszukiwanie
binarne, które jest znacznie efektywniejsze. Wymaga jednak
uporządkowania danych w strukturze.
 24
Rysunek 11 powinien być okazją do zastanowienia się, czy
przedstawienie algorytmu w formie schematu blokowego jest
dobrą formą zapisu algorytmów.
s t a r t
Pobierz: t[ N ], x
i
0

t[i] < > x and i < N-1
N
t[i] < > x
T
T N
i
i + 1

Zwróć: i
Wyprowadz

"Nie ma takiego elementu"
s t o p
pobierz: N, x, wartości tablicy t[N];
jest = 0; //zakładamy,że wartość x nie występuje
i=0;
while((jest = = 0) and (i if( t[i]= =x ) jest =1; else i=i+1;
if(jest = = 1) wyprowadz
: i;
else wyprowadz
sygnał  Nie ma takiego elementu
Rys. 11. Algorytm wyszukiwania elementu o zadanej wartości
zapisany w postaci schematu blokowego, oraz w
postaci programu, zapisanego w języku C++
Sygnał, o którym mowa powyżej, powinien mieć postać
pewnej szczególnej wartości, której wystąpienie w tablicy nie
jest możliwe.
 25
Następny przykładowy algorytm wyszukuje najmniejszy
element tablicy jednowymiarowej. Tego typu operacje są
wykonywane równie często, jak, przedstawione wyżej,
wyszukiwanie elementu o zadanej wartości
Zanim jednak przejdziemy do algorytmu rozwiązującego ten
problem zauważmy, że aby mógł być on w ogóle
rozwiązywalny, na elementach tablicy musi być określona
pewna relacja liniowego porządku, która polega na
możliwości wykonywania operatorów relacyjnych (< d" > e" =
`") w zbiorze wartości, znajdujących się w tablicy
wprowadz
wartości do tablicy t[N];
t_min=t[0];
i_min=0;
for (int i=1; i<=N-1; i++)
if( t[i] {
t_min=t[i];
i_min=i;
}; wyprowadz
: t_min, i_min
Rys. 12. Algorytm wyszukiwania najmniejszego elementu w
tablicy jednowymiarowej, zawierającej nie
powtarzające się wartości, w formie fragmentu
programu w języku C/C++
5.1.2. Wyszukiwanie połówkowe (binarne)
Zaprezentowany powyżej algorytm wyszukiwania elementu
tablicy miał cechy przeszukiwania liniowego. Jego schemat
jest prosty i naturalny:
 26
1. Pobierz pierwszy element rozpatrywanej struktury,
2. Sprawdz
, czy analizowany element jest elementem
poszukiwanym
Jeśli TAK  zakończ działanie algorytmu,
Jeśli NIE  pobierz kolejny element i roz-
pocznij realizację tego punktu
od początku.
Powyższy schemat sugeruje rekurencyjną wersję algorytmu.
W odniesieniu jednak do struktur liniowych o
nieskomplikowanej budowie, takich jak: tablice, pliki, czy
nawet listy liniowe, stosowanie rekurencji nie jest potrzebne.
Wystarczy zwykły proces iteracyjny.
Zauważmy, że dla struktur liniowych uporządkowanych,
takich jak: tablice, pliki i listy, średni czas wyszukania
elementu można skrócić o połowę. Bezcelowym jest bowiem
dalsze przeszukiwanie struktury po stwierdzeniu, że jej
elementy mają wartości wyższe (dla struktury
uporządkowanej rosnąco), niż wartość elementu
wyszukiwanego.
Poznamy teraz algorytm przeszukiwania połówkowego
zwany czasem przeszukiwaniem binarnym, który podobnie
jak omówione wyżej algorytmy wykorzystuje uporządkowanie
elementów struktury liniowej, a jednocześnie pomysł, na
którym opiera się idea, rozpatrywanych w dalszej części
wykładu, drzew binarnych poszukiwań.
Poniżej przedstawiono ogólny schemat algorytmu
przeszukiwania połówkowego dla uporządkowanej rosnąco,
jednowymiarowej, N-elementowej tablicy liczb całkowitych
t[N]. Szukamy elementu o kluczu równym zadanej wartości x.
 27
1. Jeśli wartość x jest mniejsza od klucza pierwszego
elementu rozpatrywanej tablicy, lub większa od
klucza ostatniego elementu rozpatrywanej
tablicy element o kluczu x nie istnieje, koniec.
2. Jeśli analizowana tablica zawiera co najmniej 2
elementy podziel tablicę na połowę,
wykorzystując operator dzielenia całkowitego.
Niech middle oznacza indeks pierwszego elementu
prawej części tablicy,
Jeśli analizowana tablica zawiera 1 element niech
middle będzie indeksem tego elementu,
3. Jeśli x = = t[middle] znaleziono, koniec.
Jeśli analizowana tablica zawiera 1 element
element o kluczu x nie istnieje, koniec.
4. Jeśli x < t[middle], to element o kluczu x znajduje
się w lewej części tablicy (jeśli istnieje) przejdz

do punktu 2 przyjmując, że analizowaną tablicą jest
lewa jej część,
5. Jeśli x > t[middle], to element o kluczu x znajduje
się w prawej części tablicy (jeśli istnieje) przejdz

do punktu 2 przyjmując, że analizowaną tablicą jest
prawa jej część.
Intuicja podpowiada nam, że korzyści, jakie osiągamy
stosując algorytm wyszukiwania połówkowego, zamiast
wyszukiwania liniowego, powinny być znaczne.
Rzeczywistość przerasta jednak wszelkie oczekiwania, jego
złożoność obliczeniowa jest bowiem O (log2 N), wobec
liniowej złożoności obliczeniowej algorytmu wyszukiwania
liniowego O (N).
 28
Złożoność obliczeniowa algorytmu, inaczej zwana kosztem
algorytmu jest funkcją podającą jak w sytuacji najgorszego
przypadku rośnie czas realizacji algorytmu w miarę
zwiększania rozmiarów zadania. Rozmiarem zadania,
polegającego na wyszukiwaniu elementu w jednowymiarowej
tablicy, będzie N, tj. ilość elementów tej tablicy.
Załóżmy przykładowo, że uporządkowana tablica zawiera aż
10 000 elementów. Średnia ilość porównań kluczy kolejnych
elementów tablicy z wartością poszukiwaną x wynosi przy
wyszukiwaniu liniowym 10000 / 2 = 5 000 porównań, podczas
gdy przy wyszukiwaniu połówkowym - nie więcej niż
log210 000, to jest około 13 porównań. Wynik jest
oszałamiający.
Natomiast dla tablic o małych rozmiarach nie warto używać
aż tak złożonego algorytmu, gdyż zysk czasowy będzie
niewielki. Na przykład, dla tablicy zawierającej 10
elementów, algorytm wyszukiwania liniowego będzie musiał
wykonać średnio 5 porównań, podczas gdy algorytm
wyszukiwania połówkowego potrzebuje nie więcej niż 3-4
powtórzenia, znacznie bardziej złożonej, pętli iteracyjnej.
5.2. Algorytmy sortowania tablic
Sortowanie tablic jest procesem, którego wynikiem
końcowym jest ustawienie elementów tablicy w kolejności
zgodnej z wybraną relacją liniowego porządku, lub w
porządku odwrotnym.
Opracowano wiele algorytmów sortowania tablic. Sortowanie
jest wdzięcznym zagadnieniem dydaktycznym, pokazującym
jak ten sam, niezbyt skomplikowany problem, rozwiązać
 29
można na wiele różnych sposobów, opartych na bardzo
różnych pomysłach.
Algorytmy sortowania oceniać będziemy biorąc pod uwagę
niżej wymienione własności (pierwsze trzy z nich mogą
charakteryzować dowolne algorytmy, dwie ostatnie dotyczą
wyłącznie algorytmów sortowania):
5.2.1. Cechy algorytmów sortowania:
" prostota algorytmu,
Ta cecha jest dość istotna. Algorytmy o prostej
strukturze, oparte na prostym pomyśle, można łatwo
modyfikować i dostosowywać do aktualnych potrzeb
" zajętość pamięci,
Ta cecha jest bardzo istotna. Na ogół bowiem sięgamy do
metod tak zwanego sortowania w miejscu, zwanych
inaczej metodami  in situ (łac.). Ich zapotrzebowanie na
dodatkową pamięć ogranicza się na ogół do wielkości
zajmowanej przez wartość pojedynczego elementu
tablicy.
" koszt algorytmu
Musimy założyć, że rozmiarem zadania, polegającego na
sortowaniu jednowymiarowej tablicy, będzie N, tj. ilość
elementów tej tablicy. Większość algorytmów sortowania
charakteryzuje się kosztem O(N2), wymaga bowiem
dwóch pętli iteracyjnych, przy czym jedna z nich jest
zanurzona w drugiej.
" wrażliwość na uporządkowanie sortowanej tablicy,
Z tego punktu widzenia algorytmy sortowania
dzielić będziemy na:
- całkowicie niewrażliwe na uporządkowanie,
- częściowo wrażliwe na uporządkowanie,
 30
- całkowicie wrażliwe na uporządkowanie.
W pierwszej grupie znajdą się algorytmy, dla których
uporządkowanie tablicy (pierwotne, bądz
uporządkowanie
powstałe w trakcie sortowania) nie wpływa w sposób
zasadniczy na czas realizacji algorytmu.
Za algorytmy częściowo wrażliwe na uporządkowanie
uznamy te algorytmy sortowania, które w sposób znamienny
ograniczają ilość wykonywanych operacji w trakcie procesu
sortowania (np. poprzez zawieszenie wykonywania
pewnych pętli wewnętrznych).
Algorytmy sortowania całkowicie wrażliwe na
uporządkowanie potrafią w trakcie realizacji algorytmu,
niejako przy okazji, stwierdzić uporządkowanie tablicy
(pierwotne, bądz
powstałe w dowolnym momencie procesu
sortowania), przerywając natychmiast proces sortowania.
Niżej przedstawiono ilustracje do czterech, wybranych metod
sortowania tablic. Dokładne omówienie przebiegu procesu
sortowania w tych przykładach zostanie podane na
wykładzie.
5.2.2. Sortowanie przez proste wstawianie
a)
indeksy 0 1 2 3 4
t
7 1 6 4 3
b)
indeksy 0 1 2 3 4
t
1 7 6 4 3
i
 31
3
c) x
indeksy 0 1 2 3 4
t
1 6 7 4 3
i j
Rys. 13 Algorytm sortowania przez proste wstawianie
a) stan wyjściowy, b) stan po zakończeniu pierwszej
iteracji, c) ilustracja procesu przepisywania
elementów
5.2.3. Sortowanie przez prostą zamianę (sortowanie
bąbelkowe)
7 1 1 1 1
7
1 i 7 6 6 6
6 6 i 7 4 4
4 4 4 i 7 3
________
3 3 3 3 7 i
Rys. 14. Algorytm sortowania bąbelkowego
 32
5.2.4. Algorytm sortowania przez podział (QuickSort)
5 2 7 1 3 4 6 8
2 1 3 4 7 6 8
3 4 6 8
1
Rys. 15 Idea algorytmu sortowania szybkiego QuickSort
5.2.5. Sortowanie z użyciem dodatkowej tablicy
Załóżmy, że elementami tablicy są rekordy (na rys. 16 w
owalu), z których każdy zawiera szereg pól. Jedno z nich
zostało wybrane jako klucz sortowania. Zaprezentowana niżej
metoda sortowania sprowadza się do wytworzenia dodatkowej
tablicy (zwanej tablicą indeksową), której pierwszy wiersz
przechowuje, ustawione w porządku rosnącym, klucze z
oryginalnej tablicy a drugi - odpowiadające kluczom indeksy.
indeksy 0 1 2 3 4
klucz 7 1 6 4 3
... ... ... ... ...
... ... ... ... ...
... ... ... ... ...
a)
klucz 1 3 4 6 7
indeksy 1 4 3 2 0
b)
 33
Rys. 16 Tablica indeksowa b) powstała z posortowania
wejściowej tablicy rekordów a).
Owalem zaznaczono pojedynczy rekord.
Metoda ta wymaga użycia dodatkowej tablicy, w zamian 
pozwala zachować sortowaną tablicę w stanie pierwotnym, jak
również generować wiele tablic indeksowych wg różnych
kluczy. Ocenę złożoności czasowej pozostawmy czytelnikowi.
6. Algorytmy rekurencyjne
n * silnia(n-1) dla n > 0
silnia(n) =
1 dla n = 0
fib(n-1) + fib(n-2) dla n > 1
fib(n) =
1 dla n = 0,1
Rys. 17. Funkcje rekurencyjne  postać analityczna
int silnia( int n )
{ // n jest dowolną liczbą naturalną
if( n > 0 ) return n*silnia( n-1);
else return 1;
}
Rys.18 Funkcja rekurencyjna zapisana w języku C\C++
 34
silnia(3) = 3 * silnia(2)
2 * silnia(1)
1 * silnia(0)
1
Rys. 19. Przebieg obliczeń wartości funkcji rekurencyjnej
silnia(3)
fib(n-1) + fib(n-2) dla n > 1
fib(n) =
1 dla n = 0,1
n 0 1 2 3 4 5 6 7 8 ...
fib(n) 1 1 2 3 5 8 13 21 35 ...
Rys. 20. Ciąg liczb Fibonacciego
 35
5
3
4
3 2 2
1
2 1 1 0 1 0
0
1
Rys. 21. Drzewo wywołań rekurencyjnych dla
wywołania fib(5)
6.1.Rekurencja ogonowa
Z rekurencją ogonową mamy do czynienia, kiedy wywołanie
rekurencyjne jest ostatnim poleceniem algorytmu
rekurencyjnego. Wtedy rekurencja symuluje pętlę iteracyjną.
Jeśli wywołanie rekurencyjne nie jest ostatnim wywołaniem,
na każdym poziomie wywołania, algorytm wracając na dany
poziom, wykonuje dalsze czynności kończące algorytm.
 36
Pojęcia, których znajomość jest niezbędna:
" głębokość rekurencji,
" liczba wywołań rekurencyjnych,
" maksymalna zajętość pamięci.
s = 1;
for( int i=1; i<=n; i++) s:=s*i;
Rys. 22. Iteracyjna postać algorytmu obliczania
wartości silnia(n) dla n e"
e" 0
e"
e"
0
1
1
2
n i
3 4
zm. a) s
6 b)
tymczasowa
stos stos
dla zmiennych dla zmiennych
Rys. 23. Derekursywacja
Na rys 23 porównano stosy dla zmiennych dla algorytmu
realizującego wywołanie funkcji silnia(3):
a) rekurencyjnego, w chwili po ostatnim wywołaniu
rekurencyjnym silnia(0),
b) iteracyjnego, po zakończeniu procesu iteracji
 37
6.2. Rekurencja zagnieżdżona
Przykładem funkcji z rekurencją zagnieżdżoną jest podana w
1928 przez W. Ackermanna funkcja
m+1 jeśli n = 0
A(n,m) = A(n-1,1) jeśli n>0, m=0
A(n-1, A(n,m-1)) w pozostałych przyp.
Zagnieżdżenie rekurencji, dotyczące parametru m, powoduje
nieprawdopodobnie gwałtowne zapotrzebowanie na czas
obliczeń ze wzrostem m. Obliczono, że
16
A(1,4)=22 -3=265536-3
co jest liczbą nieporównanie większą od liczby wszystkich
atomów we wszechświecie (obecnie szacuje się, że liczba ta
jest rzędu 1080). Definicję funkcji Ackermana bardzo łatwo
jest zapisać w postaci funkcji rekurencyjnej, natomiast
zapisanie jej w formie innej, niż rekurencyjna, jest bardzo
kłopotliwe.
Koniec części 2