1
[email protected]
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
[email protected]
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
[email protected]
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
[email protected]
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.
[email protected]
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.
[email protected]
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.
[email protected]
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.
[email protected]
[email protected]
4
Notranje sortiranje
•
Vsi algoritmi za urejanje (sortiranje) podatkov
slonijo na eni od treh osnovnih tehnik:


izbiranju


vstavljanju


premenami
[email protected]
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.
[email protected]
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.
[email protected]
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
}
[email protected]
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;
}
}
[email protected]
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
[email protected]
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).
[email protected]
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.
[email protected]
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.
[email protected]
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.
[email protected]
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
č
.
[email protected]
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.
[email protected]