VISOKA POSLOVNA ŠKOLA STRUKOVNIH STUDIJA
BLACE
SEMINARSKI RAD
Predmet:
Algoritmi i struktura podataka
Tema:
Unutra
Š
nje sortiranje algoritama
Student: Profesor:
Marko Jovanovic 57/07 III dr. Branislav Jevtović
2
SADRZAJ
UVOD
…………………………………………………………………………………………
3
1.
Sortiranje poređenjem
..................................................................................
5
1.1 Metodi umetanja
...........................................................................................
5
1.2
Metodi selekcije
............................................................................................
8
1.3 Metodi zamene
............................................................................................
14
2.
Metodi sortiranja linearne složenosti
……………………………
17
2.1 Sortiranje brojanjem
………………………………………………...….
17
2.2 Adresno sortiranje
………………………………………………….....…
18
2.3
Radix
sortiranje
………………………………………………………...…
19
3.
Poređenje efikasnosti metoda unutrašnjeg sortiranja
...
20
4.
Primena principa sortiranja – statistika poretka
................
21
4.1 Određivanje minimuma i maksimuma
…..........................................
21
4.2 Određivanje
k
-tog najmanjeg elementa
…………………………..
22
LITERATURA
……………..…………………………………………………………...
24
4
pokazivače u pomoćnom vektoru umesto samih zapisa, a krajnji poredak, prikazan
na slici 1.1b, je određen upravo vektorom pokazivača i na osnovu njega se zapisi
mogu konačno i fizički premestiti.
2 3
R
1
4 8
1 5
3 7
R
2
R
3
R
4
key
2 3
R
1
4 8
1 5
3 7
R
2
R
3
R
4
key
a)
b )
Slika 1.1 Sortiranje po adresi – stanje pokazivača: a) pre sortiranja i
b) posle sortiranja
Drugi način je ulančavanje zapisa između sebe u listu bez njihovog
premeštanja. Tada svaki zapis treba da ima i dodatno polje
link
koje ukazuje na
zapis sa sledećom vrednošću ključa, kao i spoljašnji pokazivač
first
koji pokazuje
na zapis sa najmanjim (ili najvećim) ključem (slika 1.2). Ovde se potreba za
premeštanjem izbegava prevezivanjem liste bez fizičkog pomeranja zapisa.
2 3
R
1
4 8
1 5
3 7
R
2
R
3
R
4
key
link
first
Slika 1.2 Sortiranje prevezivanjem pokazivača
Postoji više pristupa problemu unutrašnjeg sortiranja, sa mnogo varijanti
algoritama različite složenosti i ostalih karakteristika. Najopštiji način za sortiranje
je međusobno upoređivanje podataka po ključu, pa se ova grupa metoda naziva
sortiranje poređenjem
. Pokazuje se da su najbolje performanse kod ovih metoda u
srednjem i najgorem slučaju ograničene na
O
(
n
log
n
). Postoji, takođe, i jedan
manji broj metoda koji nisu zasnovani na međusobnom poređenju ključeva, već se
zasnivaju na nekim specifičnim karakteristikama ključeva, a mogu da postignu i
linearnu složenost
O
(
n
). Posle izlaganja obe grupe metoda i razmatranja njihovih
reprezentativnih tehnika, na kraju se daje opšte poređenje metoda unutrašnjeg
sortiranja.
5
1. Sortiranje poređenjem
Svi metodi ovoga tipa su zasnovani isključivo na međusobnom poređenju
vrednosti ključeva odgovarajućih zapisa koji se sortiraju. Glavni pristupi se mogu
svrstati u četiri grupe:
metodi umetanja
metodi selekcije
metodi zamene
metodi spajanja
Metodi spajanja, iako mogu da se koriste i za unutrašnje sortiranje,
predstavljaju skoro isključivi način sortiranja podataka na spoljašnjim uređajima.
U izlaganju u okviru svake grupe se postupno počinje sa
direktnim metodima.
Ovi
metodi dobro odslikavaju osnovne principe, jer su jednostavni, kratki i laki za
razumevanje.
1.1 Metodi umetanja
Ova grupa metoda se zasniva na principu postepenog uređivanja niza, tako
što se u svakom trenutku održava uređeni i neuređeni deo. U svakom koraku se
uzima jedan element iz neuređenog dela i umeće na odgovarajuće mesto u
uređenom delu, koji na taj način raste. Predstavnici ove grupe metoda su:
direktno umetanje
umetanje sa smanjenjem inkrementa
Direktno umetanje
Osnovni princip se najbolje odslikava u metodu
direktnog umetanja
. U
početku se uređeni deo sastoji samo od prvog elementa niza, a u neuređeni deo
spadaju svi ostali elementi. Neka se posle
i
- 1 koraka u uređenom delu nalaze
elementi
a
1
...
a
i
-1
. Tada se u koraku
i
uzima prvi element iz neuređenog dela
a
i
i
ubacuje na mesto koje mu po neopadajućem poretku odgovara u uređenom delu,
čime se ovaj deo povećava za jedan element. Sortiranje se završava kad nema više
elemenata u neuređenom delu. Direktno umetanje je ilustrovano po koracima za
dati skup ključeva na slici 1.3. Algoritam za sortiranje direktnim umetanjem je
7
dela koji su veći od tekućeg elementa pomeraju za po jedno mesto naviše i tako
prave mesto za njegovo umetanje. Metod je stabilan jer kad ključ koji se umeće
dođe do jednakog ključa u uređenom delu, on se stavlja neposredno iza njega.
Najbolje performanse direktno umetanje postiže kada je niz već uređen.
Tada je potrebno samo jedno poređenje u svakoj iteraciji što daje
C
min
=
n
- 1, a svi
elementi ostaju na svojim mestima. Prema tome, vremenska složenost je
O
(
n
).
Umetanje sa smanjenjem inkrementa
Metod prvo razdvoji početni niz na grupe tako što u svaku grupu svrstava
elemente na ekvidistantnim pozicijama u nizu. Ovaj razmak između elemenata u
grupi se naziva
inkrementom
h
1
. Broj grupa, naravno, odgovara vrednosti
inkrementa. Zatim se ove grupe posebno sortiraju primenom metoda direktnog
umetanja i niz postaje
h
1
-sortiran. U narednom koraku u nizu koji je nastao posle
prvog koraka inkrement se smanjuje na
h
2
<
h
1
i tako formira manji broj grupa sa
većim brojem elemenata, pa se one opet nezavisno sortiraju. U svakom sledećem
koraku isti postupak se ponavlja sa smanjenim inkrementom. Na kraju se postupak
završava svođenjem inkrementa na 1 što znači da je čitav niz jedna grupa čijim se
sortiranjem dobija konačan rezultat. Ovaj poslednji, jedinični korak garantuje
potpunu sortiranost niza. Na slici 1.4 demonstriran je rad ovog metoda. U prvom
koraku inkrement je 4, pa postoje četiri grupe od po 2 elementa, da bi se u drugom
koraku inkrement smanjio na 2, a u trećem, poslednjem koraku na 1.
0
6
2 7
5 7
6 5
7 5
6 5
7 5
6
5 7
9 9
2 7
0
9 6
h
1
= 4
6 5
2 7
0
5 7
9 9
7 5
6
9 6
h
2
= 2
0
2 7
6
5 7
6 5
7 5
9 9
9 6
h
3
= 1
9 6
9 9
Slika 1.4 Umetanje sa smanjenjem inkrementa
Algoritam sortiranja sa smanjenjem inkrementa je realizovan procedurom
SHELL-SORT. Pored pretpostavke, kao i ranije, da se podaci za sortiranje nalaze u
nizu
a
[1:
n
], ovde se pretpostavlja da se vrednosti inkremenata nalaze u nizu
h
[1:
t
].
SHELL-SORT(
a
,
h
)
for
i
= 1
to
t
do
inc
=
h
[
i
]
