VISOKA POSLOVNA ŠKOLA STRUKOVNIH STUDIJA
BLACE
SEMINARSKI RAD
PREDMET:
Algoritmi i strukture podataka
TEMA:
Složenost unutrašnjeg sortiranja
Student:
Simonović Filip R39/09
Mentor:
dr Branislav Jevtović
Filip Simonović R39/09 Seminarski rad
Slika 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 2). Ovde
se potreba za premeštanjem izbegava prevezivanjem liste bez fizičkog pomeranja zapisa.
Slika 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.
Tema: Složenost unutrašnjeg sortiranja
4
2 3
R
1
4 8
1 5
3 7
R
2
R
3
R
4
key
lin k
first
Filip Simonović R39/09 Seminarski rad
2. 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 i metodi spajanja. Prve tri grupe se razmatraju u ovoj
glavi, a 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, pa se zato razmatraju u narednoj glavi.
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. Pomenute prednosti
se plaćaju slabijim performansama, pa tako za velike skupove podataka treba koristiti složenije, ali
efikasnije algoritme. Međutim, za male skupove podataka njihove prednosti ne dolaze do izražaja,
pa su to slučajevi gde se direktni metodi primenjuju.
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 i 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 3.
Algoritam za sortiranje direktnim umetanjem je realizovan procedurom INSERTION-SORT. Ulaz u
proceduru predstavlja neuređeni niz ključeva
a
[1:
n
], koji ona na kraju napravi uređenim.
Tema: Složenost unutrašnjeg sortiranja
5
Filip Simonović R39/09 Seminarski rad
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.
Implementacija gornjeg algoritma može da se učini i efikasnijom tako što se pre sortiranja
stavi graničnik u
a
[0] čija vrednost odgovara minimalnom ključu u nizu. Tada nema potrebe da se u
unutrašnjoj petlji proverava da li je
j
veće od nule, jer tekući element onda ne može da ide dalje od
pozicije
a
[1].
Umetanje sa smanjenjem inkrementa
Pokazuje se da veliki broj premeštanja u metodu direktnog spajanja dolazi zbog činjenice da
se premeštaju samo susedni elementi, tako da element koji se umeće mora da pomeri u proseku oko
n
/3 ostalih. Bolji rezultati bi se mogli očekivati ako se umesto kratkih koraka omoguće skokovi na
većoj distanci. Značajno poboljšanje u ovom smeru u odnosu na direktno umetanje predložio je
Shell u metodu koji se naziva
umetanje sa smanjenjem inkrementa
ili
shellsort
.
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 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.
Tema: Složenost unutrašnjeg sortiranja
7
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
