Algorytmy przeszukiwania

Przeszukiwanie liniowe

Algorytm stosowany do poszukiwania elementu w zbiorze, o
którym nic nie wiemy. Aby mieć pewność, że nie pominęliśmy
żadnego elementu zbioru przeszukujemy go element po
elemencie. Oznacza to, że elementy zbioru zostają ustawione w
ciąg, który jest przeszukiwany od jednego z jego końców.

a

1

a

2

a

3

a

4

a

5

a

6

a

7

a

8

a

9

a

10

a

11

a

12

a

13

a

14

a

15

a

16

↑

Przeszukiwanie binarne

Algorytm ten stosuje się w sytuacji, gdy elementy zbioru maja
pewną strukturę, np. są uporządkowane. W takiej sytuacji
wykorzystujemy tą dodatkowa informację.

Przykład

Chcemy odgadnąć liczbę naturalną z przedziału [1, N]. W każdej
chwili dysponujemy podpowiedzią w postaci: „tak”, „za mało”,
„za dużo”.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

↑

11 12 13 14 15 16 17 18 19 20

↑

16 17 18 19 20

_______

↑

⎢16 ⎢17 ⎢

↑ ____

⎜ 17 ⎜ !

↑

W pojedynczym wypadku algorytm liniowy może dać szybciej
odpowiedź niż algorytm binarny, ale przy wielu próbach prawie zawsze
algorytm binarny jest szybszy.

Dane w tym przykładzie to uporządkowany ciąg liczb w tablicy
a[k],...,a[l] , gdzie k

≤ l oraz element y spełniający równość a[k] ≤ y ≤

a[l] . Trzeba znaleźć takie s (k

≤ s ≤ l ), że a[s]=y (chyba, że taki element

nie istnieje).

Algorytm (język naturalny - punkty):

1. Wprowadzenie tablicy a[k],a[k+1], ... , a[l]

2. Przypisujemy końce przedziału lewy=k, prawy=l

3. Jeśli lewy>prawy to „brak szukanej liczby” i koniec

4. W przeciwnym przypadku s=INT( (lewy+prawy)/2 )

5. Jeśli a[s] = y to wyprowadzamy s, a[s] i koniec

6. Jeśli a[s]<y to lewy=s+1, a w przeciwnym przypadku prawy=s-1 i

wracamy do pkt. 3

Algorytmy porządkowania (sortowania)

Porządkowanie występuje niemal w każdej dziedzinie wiedzy.

Jeśli elementy w zbiorze są posortowane zgodnie z jakąś regułą, np.
według liter, dat, długości itd. , to wykonywanie wielu operacji na
zbiorze staje się łatwiejsze. Dotyczy to szczególnie:

- sprawdzanie czy dany element, tzn. element o ustalonej wartości

cechy według której uporządkowano zbiór, znajduje się w zbiorze

- znalezienie elementu jeśli jest w zbiorze

- dołączenie nowego elementu w danym miejscu, tak aby zbiór pozostał

uporządkowany

Algorytm bąbelkowy

1) Algorytm opiera się na obserwacji według której, jeśli ciąg nie jest
uporządkowany, to znajdują się w nim co najmniej dwa elementy, które
są w niewłaściwych miejscach.

2) Każdą parę elementów stojącą obok siebie w niewłaściwym porządku
należy przestawić.

3) Algorytm należy skonstruować tak, aby nie pominąć żadnej pary i
porządkowanie było jak najbardziej efektywne.

4) Należy pamiętać, że po każdym porządkowaniu należy sprawdzić czy
zamiana nie spowodowała niewłaściwego uporządkowania między
innymi elementami.

5) Maksymalna ilość etapów porządkowania dla N elementów wynosi
N-1, przy czym w każdym etapie porządkowany jest co najmniej jeden
element.

Linia przerywana wskazuje miejsce powyżej którego w danym etapie nie
trzeba przeszukiwać par. Jest to miejsce, gdzie ostatnio zamieniono parę
liczb w poprzednim etapie.

Algorytm porządkowania przez wybór

1) Jeśli chcemy ustawić elementy ciągu w kolejności od najmniejszego

do największego to można wybrać najmniejszy element ciągu i
umieścić go na początku.

2) W drugim etapie należy znaleźć element najmniejszy z pozostałych

elementów (poza tymi już ustawionymi) i umieścić go na drugim
miejscu itd. .

3) Elementy należy ustawiać ekonomicznie, najlepiej w ramach tej

samej struktury danych, tzn. przestawiać elementy na właściwe
miejsca.

4) Algorytm wymaga dla N elementów N-1 etapów przy czym w

każdym etapie porządkowany jest dokładnie jeden element.

Linia przerywana wskazuje miejsce poniżej którego w danym etapie
elementy są ustawione . Jest to miejsce, w którym ustawiono element w
wyniku zamiany w poprzednim etapie.

Porządkowanie kubełkowe i pozycyjne

W

porządkowaniu kubełkowym

kolejne elementy zbioru, który

sortujemy umieszczamy w odpowiednich kubełkach.
By zbiór został całkowicie uporządkowany , kubełki wypełnione
w pierwszym etapie, muszą być opróżniane w drugim etapie,
według kolejności przypisanych im nazw. Kolejność opróżniania
kubełków jest kolejnością posortowanych elementów
rozważanego zbioru.

Kubełki są napełniane i opróżniane od dołu tworząc strukturę
danych zwaną kolejką. Kolejki pracują według zasady FIFO
(First-In, First-Out).

Inna wykorzystywana strukturą jest stos. W stosie elementy są
składowane jeden na drugim i opróżnianie stosu następuje od
góry, tj. od elementu najpóźniej wprowadzonego do stosu. Stosy
pracują według zasady LIFO (Last-In, First-Out). Stos
najczęściej występuje w iteracyjnych realizacjach algorytmów
rekurencyjnych. Częstym błędem pojawiającym się przy
programowaniu jest przepełnienie stosu („stack overflow”).

Porządkowanie kubełkowe liter wyrazu ABRAKADABRA.

Porządkowanie pozycyjne

to sortowanie słów zgodnie z

porządkiem słownikowym, czyli tak jak w słownikach i
encyklopediach. Należy zachować dwie zasady:

- jeśli dwa słowa mają jednakową długość , to szukamy w nich

pierwszej pozycji, na której się różnią i pierwsze jest to słowo,
które ma na tej pozycji „wcześniejszą” literę (np. ARAB –
ARAK)

- jeśli słowa mają nierówną długość , to albo szukamy pierwszej

pozycji, na której się różnią i litera na tej pozycji decyduje o
miejscu ustawienia słowa, albo jedno słowo jest częścią
drugiego i wtedy występuje w słowniku przed każdym słowem
, w którym jest zawarte na początku (np. BAR – BARD).

Porządkowanie słów jednakowej długości polega na
porządkowaniu ich od końca, pozycja po pozycji, z
zastosowaniem do każdej pozycji algorytmu kubełkowego.

Porządkowanie słów czteroliterowych powstałych z liter słowa
ABRAKADABRA .