Create a new version of paste:

1
bostjan.vouk@tsc.si
Programski jezik Java
Interno gradivo za predmet 
Algoritmi in programski jeziki (4. letnik)
Sortirni algoritmi
(nepre
č
iš
č
eno besedilo)
Urejanje
•
Metode sortiranja razvrš
č
amo v dve skupini, 
in sicer na notranje in zunanje metode. 
•
Notranje sortiranje
•
kadar se podatki nahajajo v hitrih pomnilnikih z 
naklju
č
nim dostopom, 
•
Zunanje sortiranje
•
podatki se nahajajo v po
č
asnejših toda ve
č
jih 
zunanjih pomnilnikih
•
trdi diski, ki temeljijo na mehansko gibljivih 
napravah z zaporednim dostopom
bostjan.vouk@tsc.si
Urejanje
•
Pri algoritmih za sortiranje nas vedno zanima tudi 
kako hitro 
uredijo elemente in koliko prostora potrebujejo za 
sortiranje. 
•
Lo
č
imo algoritme, ki sortirajo elemente 
•
na mestu, 
•
zavzamejo samo toliko prostora, kolikor ga potrebuj
ejo 
elementi
•
ki elemente prestavljajo na druge lokacije, 
•
potrebujejo ve
č
 prostora. 
•
Glede na 
č
asovno zahtevnost algoritmov pa lo
č
imo
•
preprostejše, 
•
elemente uredijo v 
č
asu O(n
2
), tem pravimo navadne 
metode
•
hitrejše
•
elemente uredijo v 
č
asu O(n log(n)), 
č
e je
bostjan.vouk@tsc.si
n število elementov
2
Urejanje
•
Kateri algoritem za sortiranje bomo izbrali, pa je 
seveda odvisno tudi od števila elementov. 
•
Navadne metode
•
preprostejše, asimptoti
č
no po
č
asnejše
•
na majhnem številu elementov prav zaradi svoje 
preprostosti veliko bolj u
č
inkovite, kot pa metode, ki 
elemente uredijo v logaritemskem 
č
asu
bostjan.vouk@tsc.si
Zunanje sortiranje
•
Algoritme ne moremo uporabiti, 
č
e podatkov, ki jih 
moramo urediti, ne moremo imeti v hitrem 
pomnilniku, ampak na zunanjih pomnilnih 
napravah, za katere vemo, da moramo do njih 
dostopati zaporedno. 
•
Na zunanjih pomnilnikih podatke shranjujemo v 
datotekah, kjer je v vsakem trenutku dosegljiv le 
en podatek. To pa je kar huda omejitev glede na 
to, da v polju lahko vsak trenutek dosežemo 
katerikoli element. 
•
To rešujemo z uporabo sortirnih metod, ki jim pravi
mo 
zunanje metode.
bostjan.vouk@tsc.si
Zunanje sortiranje
•
Pri zunanjih metodah naložimo le majhen del podatko
v v 
glavni pomnilnik, uporabimo notranjo sortirno metod
o in nato 
shranimo podatke na zunanje pomnilnike. Urejene del
e nato 
zlijemo skupaj tako, da uporabimo eno od variant so
rtiranja z 
zlivanjem, ki ga imenujemo tudi Merge sort.
•
Č
eprav smo metodo zlivanja opredelili kot zunanjo me
todo, 
je hkrati tudi notranja metoda in jo lahko uporablj
amo za 
sortiranje polj. Tudi to metodo lahko priredimo tak
o, da 
elemente zamenjujemo na mestu, torej ne potrebujemo
dodatnega prostora. Vendar je v tem primeru metoda 
v 
primerjavi z ostalimi notranjimi metodami precej 
neu
č
inkovita. 
Č
e pa ji ponudimo malo dodatnega prostora, 
postane ena izmed najhitrejših med notranjimi metod
ami.
bostjan.vouk@tsc.si
3
Zunanje sortiranje
•
Metoda Sortiranja z zlivanjem sortira elemente 
dobesedno z zlivanjem dveh zaporedij v enega, pri 
č
emer izbira med trenutno dosegljivimi elementi. 
To pa pomeni, da morata biti zaporedji urejeni, da 
potem lahko s pomo
č
jo primerjanja prvih 
elementov zaporedja dobimo eno urejeno 
zaporedje.
•
Metoda temelji na strategiji deli in vladaj. 
Zaporedje najprej razbije na podzapredja, nato pa 
jih toliko 
č
asa zliva skupaj, da dobimo eno urejeno 
zaporedje.
bostjan.vouk@tsc.si
Opis algoritma
•
Algoritem uporablja paradigmo 
deli in vladaj
. 
Za
č
ne s podtabelami velikosti 1, ki so same 
po sebi seveda urejene. Nato za
č
ne z 
zlivanjem(in sprotnim urejanjem) parov 
podtabel v ve
č
jo podtabelo in te tabele nato 
zopet zliva v ve
č
je, dokler ne zlije vseh 
elementov tabele v eno urejeno tabelo.
bostjan.vouk@tsc.si
bostjan.vouk@tsc.si
4
Notranje sortiranje
•
Vsi algoritmi za urejanje (sortiranje) podatkov
slonijo na eni od treh osnovnih tehnik:

izbiranju

vstavljanju

premenami
bostjan.vouk@tsc.si
Urejanje z vstavljanjem
•
Algoritem sortiranja z vstavljanjem uredi elemente 
tako, da po vrsti jemlje elemente in vsakega vstavi 
na svoje mesto. 
•
Za
č
ne z drugim elementom in ga primerja s prvim. 
Č
e je manjši od prvega, potem ga postavi na prvo 
mesto, sicer na drugo. Nato vzame tretji element 
in ga primerja z drugim. 
Č
e je manjši od drugega, 
ga primerja še s prvim, in v odvisnosti od rezultata 
vstavi tretji element na svoje mesto. 
•
Ta postopek ponavlja do zadnjega elementa.
bostjan.vouk@tsc.si
Opis algoritma
1.
Spremenljivki i priredi 1; 
2.
i-ti element primerjaj z elementi pred njim, 
za
č
enši z elementom na mestu i-1. Dokler ne 
naletiš na manjšega oziroma na za
č
etek polja, 
vsak element prestavi za eno mesto naprej; 
3.
Vstavi i-ti element na svoje mesto; 
4.
Spremenljivki i priredi i+1; 
•
Ponavljaj korake 2, 3 in 4, dokler spremenljivka i 
ne preseže števila elementov.
bostjan.vouk@tsc.si
5
Psevdokoda
•
Algoritem navadnega vstavljanja lahko 
zapišemo takole:
•
for(i=1; i<a.length; i++){
x=a[i];
x vstavi na pravo mesto v a
1
...a
i-1
}
bostjan.vouk@tsc.si
Metoda
•
public static void urejanjeVstavljanje(Element[] a)
{
int i, j;
Element x;
for(i=1; i<a.length; i++){
if(a[i]>a[i-1]) continue; 
//izboljšava
x=a[i];
j=i-1;
while(j>=0 && x<(a[j])){
a[j+1]=a[j];
j--;
}
a[j+1]=x;
}
}
bostjan.vouk@tsc.si
Primer
•
Podana je tabela elementov: 12,1,7,33,14,6,77,8,21,10
0.
•
Napiši, kako se spreminja vsebina tabele pri urejanju z 
vstavljanjem.

12,
1
,7,33,14,6,77,8,21,100.
1,12,
7
,33,14,6,77,8,21,100
1,7,12,
33
,14,6,77,8,21,100
1,7,12,33,
14
,6,77,8,21,100
1,7,12,14,33,
6
,77,8,21,100
1,6,7,12,14,33,
77
,8,21,100
1,6,7,12,14,33,77,
8
,21,100
1,6,7,8,12,14,33,77,
21
,100
1,6,7,8,12,14,21,33,77,
100
1,6,7,8,12,14,21,33,77,
100
bostjan.vouk@tsc.si
6
Analiza navadnega vstavljanja
•
Č
e   upoštevamo,   da   so   vse   permutacije
elementov  enako  verjetne,  lahko  ocenimo
število  C
i
primerjanj  med  elementi.  V  i-tem
pogrezanju    je    primerjanj    najve
č
i-1    in
najmanj  1,  torej  v  povpre
č
ju  i/2.  Število  M
i
premikov  oziroma  prirejanj  elementov  pa  je
C
i+2
(
č
e upoštevamo tudi prirejanje vrednosti
stražarju).
bostjan.vouk@tsc.si
Analiza navadnega vstavljanja
•
Celotno število primerjanj in premikov:
•
najmanj C
min
=n-1 M
min
=2(n-1) 
•
povpre
č
no C
ave
=1/4(n
2
+n-2) Mave=1/4(n
2
+9n-10) 
•
najve
č
 C
max
=1/2(n
2
+n)-1 M
max
=1/2(n
2
+3n-4) 
•
Najmanjše število primerjanj in premikov dobimo v 
primeru, ko so elementi že urejeni, najve
č
je pa v 
primeru, ko so elementi na za
č
etku nasprotno 
urejeni. Kar bi logi
č
no tudi pri
č
akovali, pa vendar 
pri vseh algoritmih to ne drži. Vidimo, da je 
algoritem tudi stabilen, saj medsebojni vrstni red 
elementov z enakimi klju
č
i ostane nespremenjen.
bostjan.vouk@tsc.si
Analiza navadnega vstavljanja
•
Algoritem navadnega vstavljanja seveda 
lahko izboljšamo, saj je kon
č
no zaporedje, v 
katerega vstavljamo nove elemente, že 
urejeno. Kar pa pomeni, da bi lahko uporabili 
kakšno hitrejšo metodo za iskanje mesta za 
vstavljanje naslednjega elementa. Na primer 
dvojiško iskanje, kjer naredimo primerjavo z 
elementom na sredi kon
č
nega zaporedja in 
nadaljujemo z razpolavljanjem dokler ne 
najdemo ustreznega mesta za vstavljanje.
bostjan.vouk@tsc.si
7
Analiza navadnega vstavljanja
•
To lastnost ima algoritem, ki ga imenujemo
Sortiranje z vstavljanjem s padajo
č
im
prirastkom
oziroma Shell sortiranje po
njegovem avtorju.
•
Lahko re
č
emo, da ima algoritem Navadnega 
izbiranja prednost pred Navadnim
vstavljanjem, je pa Navadno vstavljanje
nekoliko hitrejše takrat, ko so elementi na
za
č
etku že sortirani ali pa skoraj urejeni.
bostjan.vouk@tsc.si
Urejanje z izbiranjem 
•
Sortiranje z Navadnim izbiranjem temelji na 
na
č
elu iskanja oziroma izbiranja 
najmanjšega elementa. 
•
V vsakem prehodu skozi polje poiš
č
emo 
najmanjši element in ga postavimo na prvo 
mesto, kar pomeni, da so za
č
etni elementi 
polja urejeni in teh v naslednjih prehodih ne 
preverjamo ve
č
.
bostjan.vouk@tsc.si
Opis algoritma
1.
Najdi najmanjši element in ga zamenjaj s 
prvim elementom polja.
2.
Med ostalimi elementi najdi drugi najmanjši 
element v polju in ga zamenjaj z drugim 
elementom polja.
3.
Ponavljaj do predzadnjega elementa polja.
bostjan.vouk@tsc.si