Programiranje II
Beleˇ
ske za predavanja
Smer
Informatika
Matematiˇcki fakultet, Beograd
Filip Mari´
c i Predrag Janiˇ
ci´
c
2011.
4
SADR ˇ
ZAJ
4
Fundamentalni algoritmi
47
4.1
Pretraˇ
zivanje
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
47
4.1.1
Linearno pretraˇ
zivanje
. . . . . . . . . . . . . . . . . . . .
47
4.1.2
Binarno pretraˇ
zivanje
. . . . . . . . . . . . . . . . . . . .
49
4.2
Sortiranje
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
54
4.2.1
Bubble sort
. . . . . . . . . . . . . . . . . . . . . . . . . .
55
4.2.2
Selection sort
. . . . . . . . . . . . . . . . . . . . . . . . .
58
4.2.3
Insertion sort
. . . . . . . . . . . . . . . . . . . . . . . . .
60
4.2.4
Shell sort
. . . . . . . . . . . . . . . . . . . . . . . . . . .
62
4.2.5
Merge sort
. . . . . . . . . . . . . . . . . . . . . . . . . .
64
4.2.6
Quick sort
. . . . . . . . . . . . . . . . . . . . . . . . . . .
66
4.2.7
Koriˇ
s´
cenje sistemske implementacije quick sort-a
. . . . .
70
4.2.8
Empirijsko poredenje razliˇ
citih algoritama sortiranja
. . .
72
4.3
Jednostavni algebarsko-numeriˇ
cki algoritmi
. . . . . . . . . . . .
74
4.3.1
Izraˇ
cunavanje vrednosti polinoma
. . . . . . . . . . . . . .
74
4.4
Generisanje kombinatornih objekata
. . . . . . . . . . . . . . . .
75
4.4.1
Varijacije sa ponavljanjem
. . . . . . . . . . . . . . . . . .
75
4.4.2
Kombinacije
. . . . . . . . . . . . . . . . . . . . . . . . .
76
4.4.3
Permutacije
. . . . . . . . . . . . . . . . . . . . . . . . . .
77
4.4.4
Particionisanje
. . . . . . . . . . . . . . . . . . . . . . . .
79
4.5
Algoritmi zasnovani na bitovskim operatorima
. . . . . . . . . .
80
4.5.1
Primeri.
. . . . . . . . . . . . . . . . . . . . . . . . . . . .
82
5
Fundamentalne strukture podataka
89
5.1
Liste
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
5.1.1
Odnos lista, nizova i dinamiˇ
ckih blokova
. . . . . . . . . .
89
5.1.2
Elementi liste
. . . . . . . . . . . . . . . . . . . . . . . . .
90
5.1.3
Stek
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
90
5.1.4
Red
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
95
5.1.5
Dvostruko povezane (dvostruko ulanˇ
cane) liste
. . . . . .
98
5.1.6
Kruˇ
zne (cikliˇ
cne, cirkularne) liste
. . . . . . . . . . . . . .
98
5.2
Stabla
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
98
5.2.1
Binarna stabla
. . . . . . . . . . . . . . . . . . . . . . . .
99
5.2.2
Uredena binarna stabla
. . . . . . . . . . . . . . . . . . .
99
5.2.3
Izrazi u formi stabla
. . . . . . . . . . . . . . . . . . . . . 105
5.3
Grafovi
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
5.4
Heˇ
s tabele
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
II
Principi razvoja programa
107
6
Reˇ
savanje problema uz pomo´
c raˇ
cunara
109
