Podstawy Programowania 1
Sortowanie tablic jednowymiarowych
Arkadiusz Chrobot
Zakład Informatyki
12 listopada 2015
1/35
Plan
1
Sortowanie
2
Sortowanie przez wybór
3
Sortowanie przez wstawianie
4
Sortowanie bąbelkowe
5
Wyszukiwanie binarne
6
Wartość minimalna i maksymalna w posortowanej tablicy
7
Zakończenie
2/35
Sortowanie
Sortowanie
Operacje sortowania (porządkowania) i wyszukiwania danych są jednymi
z najczęściej wykonywanych przez komputery. Prof. Knuth poświęcił tym za-
gadnieniom cały trzeci tom swojej książki pt.  Sztuka programowania , który
po raz pierwszy zostały wydany na początku lat siedemdziesiątych. Można
się z niego dowiedzieć, że gdyby wszystkie komputery zostały zatrzymane,
to większość z nich wykonywałaby właśnie te operacje. Sortowanie może
dotyczyć wielu struktur danych, ale na tym wykładzie będzie nas intereso-
wało sortowanie tablic jednowymiarowych. Wartości w strukturach danych
mogą być porządkowane malejąco lub rosnąco, jeśli się one nie powtarzają
lub nierosnąco bądz
niemalejąco w przeciwnym przypadku.
3/35
Sortowanie
Sortowanie
Rodzaje sortowania
Powstało wiele algorytmów sortowania, które różnią się wieloma cechami.
Sortowanie wewnętrzne przeprowadzane jest w całości w pamięci operacyjnej
komputera1. Sortowanie wewnętrzne oznacza porządkowanie danych umiesz-
czonych w pamięci masowej. Sortowanie stabilne zachowuje początkowy
względny porządek jednakowych wartości, np. jeśli mamy w tablicy dwie
liczby 10, które oznaczymy jako 10 i 10 , to po posortowaniu tej struktury
danych 10 nadal będzie przed 10 . Jeśli sortowanie jest niestabilne, to 10
znajdzie się przed 10 . W przypadku liczb taka cecha ma niewielkie znaczenie,
ale w przypadku innych typów danych może być bardzo pomocna. Algorytmy
sortujące w miejscu (łac. in situ) nie zwiększają zapotrzebowania na miejsce
w pamięci operacyjnej w trakcie wykonywania ich kolejnych kroków. Dzię-
ki temu to zapotrzebowanie daje się przewidzieć przed ich rozpoczęciem.
W dalszej części wykładu skupimy się na sortowaniu liczb naturalnych, ale
inne dane (np. znaki) też mogą być porządkowane przez komputer.
1
Dla zainteresowanych: pomija się tu kwestię pamięci wirtualnej.
4/35
Sortowanie
Sortowanie
Przykładowe algorytmy
Sortowanie zostanie omówione na tym wykładzie na przykładzie trzech al-
gorytmów sortujących tablicę jednowymiarową. Wszystkie te algorytmy sto-
sują sortowanie w miejscu i wewnętrzne. Dwa oferują sortowanie stabilne,
a trzeci (sortowanie przez wybór) można zmodyfikować tak, aby też tak
sortował. Ich efektywność dla tablic o małej liczbie elementów jest również
porównywalna. Wszystkie zostaną omówione w wersji, która sortuje tablicę
rosnąco/niemalejąco, ale zostaną podane informacje, jak przekształcić je,
aby tablica była porządkowana odwrotnie.
5/35
Sortowanie przez wybór
Sortowanie przez wybór
Opis algorytmu
Algorytm sortowania przez wybór (ang. selection sort) jest stosunkowo pro-
sty. Został on opracowany na bazie algorytmu wyszukiwania minimum w ta-
blicy nieposortowanej (nieuporządkowanej). Jego działanie opiera się na spo-
strzeżeniu, że w tablicy posortowanej najmniejsza wartość powinna się zna-
lez
ć w pierwszym elemencie. Zatem znalez
ć element o takiej wartości w całej
tablicy i jeśli nie jest on pierwszym jej elementem, to jego wartość należy za-
mienić miejscami z wartością elementu pierwszego. To postępowanie należy
powtórzyć wyłączając pierwszy element i porządkując drugi. Te powtórze-
nia powinny trwać tak długo, aż zostaną uporządkowane wartości dwóch
ostatnich elementów w tablicy.
6/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
Następny slajd pokazuje wizualizację sortowania tablicy o pięciu elemen-
tach zawierającej liczby naturalne przy pomocy algorytmu sortowania przez
wybór. Pomarańczowa strzałka pokazuje na element, którego wartość jest
bieżąco porządkowana, a fioletowa, na element, który ma najmniejszą war-
tość, spośród tych, które należą do fragmentu tablicy zawierającego porząd-
kowany element i wszystkie elementy leżące na prawo od niego. Element
porządkowany jest dodatkowo zaznaczony na szaro. Element oznaczony na
zielono, to ten, którego wartość została już uporządkowana, a czerwony, to
ten, którego wartość musi jeszcze być uporządkowana. W wizualizacji pomi-
nięto kroki wyszukiwania elementu o najmniejszej wartości. Są one podobne
do tych w algorytmie znajdowania wartości minimalnej w nieuporządkowanej
tablicy.
7/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
15 32 8 16 4
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 32 8 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 32 8 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 32 8 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 32 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 32 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 32 16 15
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 15 16 32
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 15 16 32
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 15 16 32
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 15 16 32
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Symulacja
4 8 15 16 32
8/35
Sortowanie przez wybór
Sortowanie przez wybór
Implementacja
void selection_sort(int array[])
{
int i,j;
for(i=0; iint min = i;
for(j=i+1; jif(array[min]>array[j])
min = j;
if(min!=i)
swap(&array[min],&array[i]);
}
}
9/35
Sortowanie przez wybór
Sortowanie przez wybór
Komentarz do implementacji
Licznik zewnętrznej pętli for wyznacza kolejny element tablicy, którego
wartość powinna być uporządkowana (odpowiednik pomarańczowej strzałki
z wizualizacji). Wewnętrzna pętla for realizuje algorytm wyszukiwania naj-
mniejszej wartości we fragmencie tablicy zawierającym element porządko-
wany i wszystkie inne, które są położone na prawo od niego. Proszę zwrócić
uwagę, że tym razem nie tyle interesuje nas sama wartość, co jej położenie,
a więc indeks elementu, który ją zawiera (odpowiednik fioletowej strzałki).
Jeśli po zakończeniu pętli wewnętrznej okaże się, że zmienna min wskazuje
na inny element niż i (strzałki się nie pokrywają), to wartości elementów
indeksowanych przez te zmienne są zamieniane miejscami. Implementacja
funkcji swap() została podana na poprzednim wykładzie. Aby ten algo-
rytm sortował stabilnie wystarczy ostrą nierówność w pierwszej instrukcji
warunkowej zamienić na nieostrą. Jeśli zmienimy jej znak, to funkcja będzie
sortowała malejąco/nierosnąco. Aby podnieść efektywność tego algorytmu
można zmodyfikować go tak, aby porządkował tablicę  z obu końców szu-
kając jednocześnie wartości minimalnej i maksymalnej.
10/35
Sortowanie przez wybór
Funkcja swap()
Inna implementacja (ciekawostka)
void swap(int *first, int *second)
{
*first ^= *second;
*second ^= *first;
*first ^= *second;
}
Zamieszczona wyżej funkcja dokonuje wymiany zawartości dwóch zmien-
nych przekazanych jej przez adres, ale bez użycia dodatkowej zmiennej. Jest
to możliwe dzięki wykorzystaniu odwracalności działania operatora ^ (xor).
Zaletą tego rozwiązania jest mniejsze zużycie pamięci, ale w porównaniu
z  klasyczną implementacją jest ona wolniejsza i nie daje się wprost zasto-
sować do innych typów zmiennych (np. double). Istnieją też inne warianty
tego rozwiązania, stosujące inne operatory, z też podobnymi ograniczeniami.
11/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Opis algorytmu
Innym rozwiązaniem problemu sortowania tablic jednowymiarowych jest al-
gorytm sortowania przez wstawianie (ang. insertion sort). Działanie tego
algorytmu przypomina zachowanie amatorów gier karcianych, którzy wsta-
wiają do swojej tali nowo pobraną kartę, przesuwające te, które już trzymają
w rękach. Algorytm ten rozpoczyna porządkowanie tablicy od jej drugiego
elementu, porównując jego wartość z tą, która jest w pierwszym elemencie.
Jeśli ta ostatnia jest większa, to przesuwa ją (kopiuje w prawo), a w jej
miejsce wstawią tę z drugiego elementu. Podobnie postępuje dla wartości
z trzeciego elementu. Porównuje ją z wartościami elementów leżących na
lewo od niego. Tak długo, jak są one większe przesuwa w prawo. Jeśli napo-
tka wartość większą lub równą od tej, którą porządkuje, to wstawia ją przed
tym elementem. Czynności te powtarza dla wartości pozostałych elementów
tablicy tak długo, aż wszystkie uporządkuje.
12/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
Kolejny slajd zawiera wizualizację porządkowania tablicy jednowymiarowej
przez algorytm sortowania przez wstawianie. Na szaro zaznaczony jest ele-
ment, z którego pobierana jest porządkowana wartość. Jest ona przesuwana
nad elementami z których wartościami jest porównywana. Proszę zauważyć,
że zamiast typowych wymian wartości elementów, jak w algorytmie sortowa-
nia przez wybór jest tu stosowane kopiowanie w prawo wartości większych
od tej, która jest porządkowana. Takie operacje można nazwać półwymia-
nami. Podobnie jak w poprzedniej symulacji elementy oznaczone na zielono
są uporządkowane, a te na zaznaczone na czerwono wymagają jeszcze upo-
rządkowania.
13/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
15 32 8 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
32
15 32 8 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
8
15 32 8 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
8
15 32 32 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
8
15 15 32 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
16
8 15 32 16 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
16
8 15 32 32 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
16
8 15 32 32 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4
8 15 16 32 4
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4
8 15 16 32 32
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4
8 15 16 16 32
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4
8 15 15 16 32
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4
8 8 15 16 32
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Symulacja
4 8 15 16 32
14/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Implementacja
void insertion_sort(int array[])
{
int i;
for(i=1;iint key = array[i];
int j = i-1;
while(j>=0&&array[j]>key) {
array[j+1]=array[j];
j--;
}
array[j+1]=key;
}
}
15/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Komentarz do implementacji
Implementacja tego algorytmu jest bardziej skomplikowana, niż implemen-
tacja sortowania przez wybór. Licznik pętli for wyznacza element, którego
wartość ma zostać uporządkowana. W pętli while ta wartość porównywana
jest z wartościami elementów leżących na lewo do niej w tablicy. Jeśli są
one większe, to funkcja przesuwa je w prawo o jeden element. Dopiero wte-
dy gdy zostanie napotkana wartość mniejsza lub równa tej porządkowanej,
to ta ostatnia jest wstawiana przez elementem zawierającym taką wartość.
W przypadku gdy pętla wewnętrzna zatrzyma się  poza tablicą, to war-
tość ze zmiennej key jest kopiowana do pierwszego elementu tablicy. Aby ta
funkcja sortowała malejąco/nierosnąco wystarczy zmienić znak w wyrażeniu
array[j]>key.
16/35
Sortowanie przez wstawianie
Sortowanie przez wstawianie
Porównanie z sortowaniem przez wybór
Można zaobserwować, że sortowanie przez wstawianie jest pod pewnymi
względami przeciwieństwem sortowania przez wybór:
sortowanie przez wybór dopasowuje wartość do elementu, a sortowanie
przez wstawianie element do wartości,
sortowanie przez wybór przegląda tablicę  w prawo , a sortowanie
przez wstawianie  w lewo .
17/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Opis algorytmu
Istnieje kilka wersji algorytmu sortowania bąbelkowego (ang. bubble sort).
W jednej z nich algorytm ten przegląda tablicę od końca, po jednym ele-
mencie i porównuje wartości bieżącego elementu z jego sąsiadem z lewej
strony. Jeśli nie znajdują się one w oczekiwanym porządku, to algorytm za-
mienia je miejscami. Tablica jest przeglądana w ten sposób wielokrotnie, aż
do całkowitego jej uporządkowania. Po każdym powtórzeniu przeglądania,
co najmniej jeden element z lewej strony tablicy zyskuje prawidłową wartość
i przy kolejnej iteracji jest już pomijany.
18/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
Kolejny slajd przedstawia symulację sortowania tablicy jednowymiarowej przy
pomocy algorytmu bąbelkowego. Szary kolor oznacza parę elementów, któ-
rych wartości są bieżąco porównywane. Czerwonym kolorem zaznaczone są
elementy, które jeszcze będą sprawdzane, a zielonym te, które zostały już
uporządkowane.
19/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
15 32 8 16 4
4
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
15 32 8 4 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
15 32 4 8 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
15 4 32 8 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 15 32 8 16
16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 15 32 8 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 15 8 32 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 8 15 32 16
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 8 15 16 32
32
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 8 15 16 32
32
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Symulacja
4 8 15 16 32
32
20/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Implementacja
void bubble_sort(int array[])
{
int i,j;
for(i=0; ifor(j=NUMBER_OF_ELEMENTS; j>i; j--)
if(array[j-1]>array[j])
swap(&array[j-1],&array[j]);
}
21/35
Sortowanie bąbelkowe
Sortowanie bąbelkowe
Komentarz do implementacji
Wewnętrzna pętla for realizuje przeglądanie tablicy od końca i porównywa-
nie par sąsiadujących z sobą elementów. Zakres tego przeglądania w kolej-
nych iteracjach ogranicza licznik pętli zewnętrznej. Aby posortować tablicę
w odwrotnym porządku wystarczy zmienić znak nierówności w instrukcji
warunkowej.
22/35
Sortowanie bąbelkowe
Sortowanie - porównanie algorytmów
Wszystkie przedstawione algorytmy mają zbliżone cechy, poza stabilnością,
która w przypadku algorytmu sortowania przez wybór nie jest domyślnie za-
pewniona, ale może być łatwo zrealizowana. To co je różni, to wydajność.
Choć z teorii złożoności obliczeniowej, która zajmuje się efektywnością algo-
rytmów, wynika, że czas działania wszystkich tych algorytmów jest propor-
cjonalny do kwadratu liczby elementów tablicy2, to występują między nimi
znaczące różnice indywidualne. Algorytm sortowania bąbelkowego wypada
w tym zestawieniu najgorzej. Nie jest to najgorszy możliwy algorytm sorto-
wania, bo takim jest BogoSort, który polega na losowym przestawianiu war-
tości elementów i sprawdzaniu, czy są w odpowiedniej kolejności. Niemniej
sortowanie bąbelkowe uważane jest za antyprzykład sortowania, z uwagi na
dużą liczbę kosztownych wymian wartości elementów, jaką przeprowadza.
2
Dokładniejsza analiza złożoności czasowej algorytmów sortowania, której
wartość może zależeć od konfiguracji początkowej wartości elementów tablicy,
będzie prowadzona na zajęciach z Algorytmów i Struktur Danych.
23/35
Sortowanie bąbelkowe
Sortowanie - porównanie algorytmów
Kontynuacja
Algorytmu sortowania bąbelkowego nie należy stosować w praktyce. Niektó-
rzy informatycy proponują go w ogóle nie nauczać. Różnice w efektywno-
ści dwóch pozostałych algorytmów nie są wielkie, jednak częściej szybciej
działa sortowanie przez wstawianie niż sortowanie przez wybór. Zależy to
jednak od zastosowania. Jeśli częściej wykonywane są porównania elemen-
tów, niż zamiana ich wartości, to efektywniej działa sortowanie przez wybór.
W przeciwnym przypadku krócej tablicę sortuje algorytm sortowania przez
wstawianie.
24/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Opis algorytmu
Okazuje się, że jeśli tablica jest uporządkowana (rosnąco/niemalejąco), to
można zastosować dla niej algorytm wyszukiwania wartości znacznie szyb-
szy niż w przypadku tablic nieposortowanych. Tym algorytmem jest algorytm
wyszukiwania binarnego, nazywany także algorytmem wyszukiwania połów-
kowego. Jego działanie składa się z kilku kroków. Pierwszym jest wyznacze-
nie elementu środkowego tablicy. Jeśli tablica ma parzystą liczbę elementów,
to zostaje nim element położony na prawo od jej środka. Wartość tego ele-
mentu jest porównywana z poszukiwaną wartością. Jeśli są one sobie równie,
to zwracany jest indeks tego elementu i algorytm kończy działanie. Jeśli na-
tomiast wartość elementu środkowego jest większa od wartości szukanej, to
znaczy, że jeśli ta ostatnia w ogóle występuje w tablicy, to będzie znajdowa-
ła się we fragmencie tablicy położonym na lewo od elementu środkowego.
Jeśli wynik porównania będzie odwrotny, to znaczy, że szukana wartość mo-
że znajdować się we fragmencie położonym na prawo do środka. Algorytm
powtarza to działanie dla wyznaczonego fragmentu tablicy.
25/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Opis algorytmu - kontynuacja
Algorytm wyszukiwania binarnego tak powtarza opisane na poprzednim slaj-
dzie czynności, aż znajdzie szukaną wartość, jeśli występuje ona w tablicy,
lub gdy wyznaczony fragment tablicy będzie tak mały, że nie będzie zawierał
żadnych jej elementów. Ten ostatni przypadek występuje wtedy, gdy w ta-
blicy nie ma szukanej wartości. To, że algorytm się zawsze zatrzyma można
wywnioskować po tym, że po każdym powtórzeniu jego działania fragment
tablicy, który trzeba przeszukać staje się krótszy o około połowę. Jest to
też przyczyną tego, że ten algorytm jest szybszy od algorytmu wyszukiwania
liniowego. W przypadku wyszukiwania binarnego w każdym kroku liczba ele-
mentów, które trzeba sprawdzić redukuje się o około połowę, a w przypadku
wyszukiwania liniowego tylko o jeden. Choć opis algorytmu wyszukiwania
binarnego jest stosunkowo prosty, to jego szczegóły nastręczają problemów
w implementacji. Według Jona Bentley a algorytm ten był znany już w 1946
roku, ale jego poprawna realizacja pojawiła się dopiero w 1962.
26/35
Wyszukiwanie binarne
Wyszukiwanie binarnego
Symulacja
Kolejny slajd zawiera symulację działania algorytmu wyszukiwania połów-
kowego dla posortowanej tablicy liczby naturalnych o sześciu elementach.
Strzałki oznaczone jako down i up wyznaczają odpowiednio element począt-
kowy i element końcowy fragmentu tablicy, który ma być w danej iteracji
zbadany. Początkowo ten fragment obejmuje całą tablicę, ale wraz z wykony-
waniem kolejnych powtórzeń przez algorytm będzie się zmniejszał. Strzałka
middle wskazuje na środkowy element przeszukiwanego obszaru. Szukana
wartość została umieszczona po lewej stronie slajdu w okręgu.
27/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Symulacja
14
up
down middle
0 1 2 3 4 5
7 9 10 14 17 20
28/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Symulacja
14
up
down middle
0 1 2 3 4 5
7 9 10 14 17 20
28/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Symulacja
middle
14
up
down
0 1 2 3 4 5
7 9 10 14 17 20
28/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Implementacja
int binary_search(int array[], int value)
{
int down=0, up=NUMBER_OF_ELEMENTS;
while(down<=up) {
int middle = down+((up-down)/2);
if(array[middle]==value)
return middle;
if(array[middle]down = middle + 1;
continue;
}
if(array[middle]>value)
up = middle - 1;
}
return -1;
}
29/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Komentarz do implementacji
Zmienne wyznaczające początek, koniec i środek przeszukiwanego obszaru
tablicy są tak samo nazwane jak strzałki z symulacji. Pierwszym elemen-
tem zwracającym uwagę w tej implementacji jest wyrażenie wyznaczające
indeks elementu środkowego przeszukiwanego fragmentu tablicy. Dlaczego
nie policzyć go jako średniej arytmetycznej zmiennych down i up? Niestety
takie rozwiązanie, przy bardzo dużych tablicach, zawierających ponad miliard
elementów może doprowadzić do przekroczenia zakresu typu int przy do-
dawaniu tych zmiennych, co z kolei spowoduje błędne wyznaczenie takiego
indeksu. Wersja tu zaprezentowana jest jedną z możliwych, które pozba-
wione są tej usterki. Drugi ważny element, to wykrywanie, że w tablicy nie
ma szukanej wartości. Dzieje się tak, kiedy wartość zmiennej down będzie
większa od wartości zmiennej up i oznacza, że przeszukiwany fragment ta-
blicy nie ma zawiera żadnych jej elementów. W pętli while sprawdzany jest
odwrotny warunek, czyli czy fragment zawiera choć jeden element.
30/35
Wyszukiwanie binarne
Wyszukiwanie binarne
Komentarz - kontynuacja
Ostatni ciekawy element to wyłączanie sprawdzonego elementu środkowego
z wyliczania granic przeszukiwanego fragmentu - skoro został już spraw-
dzony, to na pewno szukanej wartości w nim nie ma, a jego pozostawienie
w przeszukiwanym fragmencie mogłoby spowodować błędne działanie algo-
rytmu. Instrukcja continue została zastosowana, aby uniknąć sprawdzania
warunku, który na pewno nie byłby spełniony. Jeśli szukana wartość nie
występuje w tablicy, to funkcja zwraca wartość -1, natomiast jeśli szukana
wartość powtarza się w tablicy, to algorytm binarny gwarantuje znalezienie
jej wystąpienia, ale niekoniecznie będzie to pierwsze wystąpienie.
31/35
Wartość minimalna i maksymalna w posortowanej tablicy
Wartość minimalna i maksymalna w posortowanej tablicy
Wyszukiwanie minimalnej i maksymalnej wartości w tablicy posortowanej
staje się wręcz trywialnie proste. Jeśli tablica jest uporządkowana rosną-
co/niemalejąco, to wartość minimalna znajduje się w jej pierwszym elemen-
cie, a maksymalna w ostatnim. Jeśli tablica jest posortowana odwrotnie, to
te wartości też umieszczone są w odwrotnej kolejności w takiej tablicy.
32/35
Zakończenie
Podziękowania
Składam podziękowania dla dra inż. Grzegorza A
ukawskiego i mgra inż.
Leszka Ciopińskiego za udostępnienie materiałów, których fragmenty zostały
wykorzystane w tym wykładzie.
33/35
Zakończenie
Pytania
?
34/35
Zakończenie
koniec
Dziękuję Państwu za uwagę.
35/35


Wyszukiwarka

Podobne podstrony:
PP1 lecture 4
PP1 lecture 5
PP1 lecture 8
PP1 lecture
PP1 lecture 7
PP1 lecture 9
PP1 lecture 2
Lecture4 Med Women Monsters Film
lecture 2
Bezhanshivili Lattices and Topology (Lecture Presentation)
wfhss conf20070503 lecture29 en
Feynman Lectures on Physics Volume 1 Chapter

Syntax lecture3
Lecture POLAND Competitiv2008
Telecommunication Systems and Networks 2011 2012 Lecture 6
PP1 laboratorium 7
CJ Lecture 6

więcej podobnych podstron