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