Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement