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.
Pobierz: t[ N ], x
i
0
N
T
T N
i
i + 1
Zwróć: i
Wyprowadź
"Nie ma takiego elementu"
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<N))
if( t[i]= =x ) jest =1; else i=i+1;
if(jest = = 1) wyprowadź: i;
else wyprowadź 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.
s t a r t
t[i] < > x and i < N-1
t[i] < > x
s t o p
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 (< ≤ > ≥ =
≠) w zbiorze wartości, znajdujących się w tablicy
wprowadź 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_min=t[i];
i_min=i;
}; wyprowadź: 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. Sprawdź, 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) → przejdź
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) → przejdź
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 (log
2
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ż
log
2
10 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(N
2
), 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ądź 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ądź 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
b)
indeksy 0 1 2 3 4
t
i
7
1
6
4
3
1
7
6
4
3
31
c) x
indeksy 0 1 2 3 4
t
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
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
1
6
7
4
3
3
7
32
5.2.4. Algorytm sortowania przez podział (QuickSort)
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)
5
2 7 1 3 4 6 8
7
6 8
2
1 3 4
3
4
1
6
8
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
Rys. 20. Ciąg liczb Fibonacciego
n
0 1 2 3 4 5 6 7 8 ...
fib(n) 1 1 2 3 5 8 13 21 35 ...
35
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.
4
3
2
2
2
3
1
1
0
1
1
0
1
0
5
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
≥≥≥≥ 0
n i
zm. a) s 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
0
1
1
2
3
6
4
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
3
2
3
2
)
4
,
1
(
65536
2
16
−
=
−
=
A
co jest liczbą nieporównanie większą od liczby wszystkich
atomów we wszechświecie (obecnie szacuje się, że liczba ta
jest rzędu 10
80
). 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