Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy

i

struktury danych

WYKŁAD 5

Dr inż. Krzysztof Pancerz

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy wyszukiwania

●

Algorytmy wyszukiwania rozwiązują problem
wyznaczenia pozycji danych elementów
(wartości) w tablicach.

●

Podstawowe algorytmy wyszukiwania:

–

wyszukiwanie liniowe,

–

wyszukiwanie binarne.

Krzysztof Pancerz

Algorytmy i struktury danych

Wyszukiwanie liniowe

●

Wejście:

–

tablica t o rozmiarze n,

–

dany element e.

●

Wyjście:

–

indeks (pozycja) elementu e w tablicy t.

Krzysztof Pancerz

Algorytmy i struktury danych

Wyszukiwanie liniowe

pozycja=-1;

for(int i=0; i<n; i++)

{

if( e==t[i]) //element został znaleziony
{
pozycja=i;
break;
}

}

cout<<pozycja;

Krzysztof Pancerz

Algorytmy i struktury danych

Wyszukiwanie binarne

●

Wejście:

–

tablica t o rozmiarze n posortowana w porządku

niemalejącym, tj.:

–

dany element e.

●

Wyjście:

–

indeks (pozycja) elementu e w tablicy t.

t

[0]t [1]t [2]...t [n−1]

Krzysztof Pancerz

Algorytmy i struktury danych

Wyszukiwanie binarne

pozycja=-1; lewy=0; prawy=n-1;

while(lewy<=prawy)

{ srodek=(lewy+prawy)/2;

if( e==tab[srodek]) //element został znaleziony

{ pozycja=srodek; break; }

else

{

if( e<tab[srodek]) //należy przeszukiwać pierwszą część
{ prawy=srodek-1; }
else

//należy przeszukiwać drugą część

{ lewy=srodek+1; }

}

}

cout<<pozycja;

Krzysztof Pancerz

Algorytmy i struktury danych

Porównanie algorytmów wyszukiwania

●

Warunki wstępne

–

Wyszukiwanie binarne: tablica musi być

posortowana

–

Wyszukiwanie liniowe: brak

●

Złożoność algorytmu

–

Wyszukiwanie binarne:

–

Wyszukiwanie liniowe:

O

log n

O

n

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytmy sortowania

●

Zadaniem algorytmu sortowania jest ustawienie

elementów (wartości) danej tablicy (listy) w

odpowiednim porządku (niemalejącym lub

nierosnącym).

●

Wejście:

Tablica o rozmiarze n: a[0], a[1], ..., a[n-1].

●

Wyjście:

Tablica posortowana w porządku niemalejącym:

a[0] ≤ a[1] ≤ ... ≤ a[n-1]

lub w porządku nierosnącym:

a[0] ≥ a[1] ≥ ... ≥ a[n-1].

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie przez selekcję (selectionsort)

●

W sortowanej tablicy (a[0], a[1], ..., a[n-1])

wybierany jest element minimalny (maksymalny),

który zamieniany jest miejscami z pierwszym

elementem tablicy (tj. a[0]).

●

Z pozostałej części tablicy (a[1], a[2], ..., a[n-1])

ponownie wybierany jest element minimalny

(maksymalny), który zamieniany jest miejscami z

drugim elementem tablicy (tj. a[1]).

●

Analogicznie proces jest kontynuowany dla

pozostałych części tablicy.

●

Sortowanie przez selekcję jest algorytmem o

złożoności O(n

2

).

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie przez selekcję (cd.)

for(i=0; i<n-1; i++)

{

min=i;
for(j=i+1; j<n; j++)
{

if( a[j]<a[min] )
{ min=j; }

}
t=a[min];
a[min]=a[i];
a[i]=t;

}

Wyszukiwanie elementu
minimalnego

Zamiana miejscami
elementów

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie przez wstawianie (insertionsort)

●

Sortowana tablica podzielona jest na dwie
części:

–

część uporządkowaną (na początku zawierającą

tylko element a[0]),

–

część nieuporządkowaną (na początku zawierającą
elementy

a[1], a[2], ..., a[n-1]

).

●

W każdym kroku kolejny element części
nieuporządkowanej przenoszony jest do części
uporządkowanej przez wstawienie go na
odpowiedniej pozycji.

●

Sortowanie przez wstawianie jest algorytmem o
złożoności

O(n

2

).

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie przez wstawianie (cd.)

for(i=1; i<n; i++)

{

j=i;
v=a[i];
while( (v<a[j-1]) && (j>0) )
{

a[j]=a[j-1]; //przesunięcie elementu a[j-1] aby zrobić

//miejsce dla elementu wstawianego

j- -;

}
a[j]=v;

}

Wyszukiwanie
odpowiedniej
pozycji dla elementu

Wstawianie elementu na
odpowiednią pozycję.

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie bąbelkowe (bubblesort)

●

Sortowanie bąbelkowe polega na zamianie
miejscami sąsiadujących ze sobą elementów
jeśli są one ustawione w nieodpowiednim
porządku.

●

Proces powtarzany jest dla nieposortowanych
części tablicy dopóty, dopóki wszystkie
elementy tablicy nie będą we właściwym
porządku.

●

Sortowanie bąbelkowe jest algorytmem o
złożoności

O(n

2

).

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie bąbelkowe (cd.)

for(i=1; i<n; i++)

{

for(j=n-1; j>=i; j--)
{

if( a[j-1]>a[j] )
{

t=a[j-1];
a[j-1]=a[j];
a[j]=t;

}

}

}

Zamiana miejscami
sąsiadujących ze sobą
elementów jeśli nie są
we właściwym porządku

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie szybkie (quicksort)

●

Sortowanie szybkie oparte jest o zasadę „dziel i
zwyciężaj” oraz rekurencję.

●

Sortowana tablica dzielona jest na dwie części
względem odpowiednio wybranego elementu
podziału. Elementy mniejsze niż element
podziału umieszczane są w lewej części tablicy
(niekoniecznie w odpowiednim porządku), zaś
elementy większe lub równe elementowi
podziału umieszczane są w prawej części
tablicy (także niekoniecznie w odpowiednim
porządku).

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie szybkie (cd.)

●

Następnie obie części tablicy sortowane są
niezależnie.

●

Sortowanie szybkie jest algorytmem o średniej
złożoności O(nlogn). W najgorszym przypadku
sortowanie szybkie ma złożoność O(n

2

).

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie szybkie (cd.)

●

Wejście:

–

a – sortowana tablica,

–

i – indeks pierwszego elementu tablicy,

–

j – indeks ostatniego elementu tablicy.

●

Wyjście:

–

a – tablica posortowana.

Krzysztof Pancerz

Algorytmy i struktury danych

Sortowanie szybkie (cont.)

quicksort(a,i,j)
{

if(i<j)
{

p=podzial(a,i,j);
quicksort(a,i,p-1);
quicksort(a,p+1,j);

}

}

Krzysztof Pancerz

Algorytmy i struktury danych

Inne algorytmy sortowania

●

Sortowanie przez scalanie (mergesort)

●

Sortowanie przez zliczanie (countsort)

●

Sortowanie pozycyjne (radixsort)

●

... i wiele innych

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie tekstu

●

Problem:

–

znaleźć wzorzec p w tekście t.

●

Wejście:

–

t – przeszukiwany tekst,

–

p - wyszukiwany wzorzec,

–

stopień dopasowania (dokładny lub przybliżony).

●

Wyjście:

–

pozycja loc wzorca p w tekście t.

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie tekstu

●

Założenia:

–

Tekst t jest umieszczony w tablicy zapisanej jako:

t[0 .. n−1],

gdzie n jest rozmiarem tablicy t.

–

Wzorzec p jest umieszczony w tablicy zapisanej

jako:

p[0 .. m−1],

gdzie m jest rozmiarem tablicy p.

–

m≤n.

Krzysztof Pancerz

Algorytmy i struktury danych

Przykład

●

Tekst jest dokumentem w pamięci komputera.

●

Wzorzec jest słowem (lub zdaniem), które
chcemy zlokalizować w dokumencie.

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie proste

●

Przeszukiwanie proste polega na
porównywaniu wzorca znak po znaku z
kolejnymi znakami w tekście aż do momentu
gdy wzorzec zostanie odnaleziony w tekście.

●

Wejście:

–

tekst t o długości n,

–

wzorzec p o długości m, gdzie m≤n.

●

Wyjście:

–

pozycja wzorca p w tekście t.

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie proste (cd.)

●

W najgorszym wypadku wzorzec nie występuje
w tekście. Algorytm działa wówczas w czasie:

●

W najlepszym wypadku wzorzec występuje na
początku tekstu. Algorytm działa wówczas w
czasie:

m

m⋅n−m1

Krzysztof Pancerz

Algorytmy i struktury danych

Przeszukiwanie proste (cd.)

i=0;

loc=−1;

while( (i+m)<=n )

{

j=0;
while( t[i+j]==p[j] )
{

j=j+1;
if(j>m) { loc=i; break; }

}
if( loc != −1 ) break;
i=i+1;

}

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Rabina-Karpa

●

Algorytmie Rabina-Karpa nie wymaga za
każdym razem porównywania całego wzorca.

●

Algorytm może być używany dla binarnych
łańcuchów znaków (tj. łańcuchów
zawierających tylko dwa symbole, np. 0 i 1).

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Rabina-Karpa (cd.)

●

Wejście:

–

tekst t o długości n,

–

wzorzec p o długości m, gdzie m≤n.

●

Wyjście:

–

pozycja wzorca p w tekście t.

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Rabina-Karpa (cd.)

●

Krok 1: Określenie parzystości wzorca p.

●

Krok 2: Dla każdego i od 0 do n−m−1
obliczenie funkcji f w następujący sposób:

f[i]=parzystość(t[i .. i+m−1])

●

Step 3: Sprawdzenie każdej pozycji loc, dla
której f[loc] jest równe parzystości wzorca p.

Krzysztof Pancerz

Algorytmy i struktury danych

Algorytm Knutha-Morrisa-Pratta

●

Dany jest wzorzec p[0 .. m-1]. Algorytm Knutha-
Morrisa-Pratta wyznacza tablicę, która pozwala
odpowiedzieć na następujące pytanie dla
każdego k<m-1: jeśli p[0 .. k] pasuje do tekstu,
to o ile pozycji możemy przesunąć wzorzec gdy
symbol (znak) p[k+1] nie pasuje do tekstu?

●

Algorytm Knutha-Morrisa-Pratta rozwiązuje
problem w czasie liniowym:

mn