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 .
