Poznamo več algoritmov za urejanje. Ločimo med algoritmi za notranje in zunanje urejanje.

Med algoritme za zunanje urejanje spada navadno zlivanje. Zanimale me bodo izboljšave navadnega zlivanja. Poznamo naslednje izboljšave navadnega zlivanja:

• uravnoteženo zlivanje,
• večsmerno zlivanje,
• navadno zlivanje in
• polifazno zlivanje (sortiranje).

V seminarski nalogi bom predstavila polifazno sortiranje. Z algoritmom za polifazno sortiranje uredimo števila v naraščajoči vrstni red. Ta algoritem spada med algoritme za zunanje urejanje in je izboljšava navadnega zlivanja.

Algoritem za polifazno sortiranje ureja podatke na datotekah. Pri tem urejanju lahko predpostavimo zaporedni oz. sekvenčni dostop.

Pri zaporednem oz. sekvenčnem dostopu se datoteko bere od začetka naprej. To pomeni, da podatke beremo po vrsti. Če hočemo prebrati podatek na mestu n moramo najprej prebrati podatek na mestu n-1. In če hočemo prebrati podatek na mestu n-1, moramo prej prebrati podatek na mestu n-2. Tako, če hočemo prebrati n-ti podatek, moramo najprej prebrati 1. podatek, nato 2. podatek,… dokler ne pridemo n-tega podatka.

Navadno zlivanje je osnova za vse algoritme zunanjega urejanja. Metoda deluje tako, da iz zaporedja bere podzaporedja dolžine k, za katere privzamemo, da so že urejena. Ta podzaporedja zapisuje na dva izhodna trakova. Nato pa podzaporedja dolžine k iz teh izhodnih trakov, zliva na vhodni trak. Na tem vhodnem traku tako dobimo urejeno podzaporedje dolžine 2*k.

Ker zlivamo čete vedno zlivamo dva seznama, ki sta naraščajoče urejena. To vemo zato, ker je četa strnjeno naraščajoče podzaporedje.

Seznama zlivamo tako, da vedno pogledamo kateri od začetkov obeh seznamov je manjši. Manjšega dodamo k novemu seznamu ter ga izbrišemo z začetka seznama kjer smo ga vzeli.

Postopek ponavljamo dokler ne izpraznimo obeh seznamov. V primeru, da en seznam izpraznimo pred drugim, v nov seznam na konec dodamo preostanek seznama.

Primer zlivanja: Sez_1 in Sez_2 zlij v Sez.
Sez_1 = 1,2,5,8,8,9
Sez_2 = 3,5,6,7,10,15,16,18

Prvi element v Sez_1 je 1, to je manjše kot prvi element v Sez_2. Dodam ga v Sez in ga izbrišem iz Sez_1.
Sez = 1
Sez_1 = 2,5,8,8,9
Sez_2 = 3,5,6,7,10,15,16,18

Prvi element v Sez_1 je 2, to je manjše kot prvi element v Sez_2. Dodam ga v Sez in ga izbrišem iz Sez_1.
Sez = 1,2
Sez_1 = 5,8,8,9
Sez_2 = 3,5,6,7,10,15,16,18

Prvi element v Sez_1 je 5, to je večje kot prvi element v Sez_2. Element iz Sez_2 dodam v Sez in ga izbrišem iz Sez_2.
Sez = 1,2,3
Sez_1 = 5,8,8,9
Sez_2 = 5,6,7,10,15,16,18

Prvi element v Sez_1 je 5, to je enako kot prvi element v Sez_2. V tem primeru je vseeno katerega najprej dodam v seznam Sez. Recimo, da najprej dodam element iz seznama Sez_1.
Sez = 1,2,3,5
Sez_1 = 8,8,9
Sez_2 = 5,6,7,10,15,16,18

Sedaj pa v seznam Sez dodam še element iz Sez_2.
Sez = 1,2,3,5,5
Sez_1 = 8,8,9
Sez_2 = 6,7,10,15,16,18

Prvi element v Sez_1 je 8, to je večje kot prvi element v Sez_2. Element iz Sez_2 dodam v Sez in ga izbrišem iz Sez_2.
Sez = 1,2,3,5,5,6
Sez_1 = 8,8,9
Sez_2 = 7,10,15,16,18

V naslednjih korakih dodam v seznam Sez števila 7,8,8 in 9.

Sedaj pa pridem do situacije, ko imam seznam Sez_1 prazen. V seznamu Sez_2 pa so gotovo vsa števila večja kot v seznamu Sez. Zato lahko števila iz seznama Sez_2 dodam na konec seznama Sez.
Sez = 1,2,3,5,5,6,7,8,8,9,10,15,16,18
Sez_1 =
Sez_2 =

Za rezultat dobim eno samo četo.

Pri polifaznem sortiranju imamo N datotek. Algoritem naenkrat prebere iz N-1 datotek in zapiše na eno samo datoteko. Datoteke iz katerih beremo imenujemo vhodne datoteke, datoteko na katero pišemo pa jo imenujemo izhodna datoteka. Na izhodno datoteko pišemo dokler ne izčrpamo ene vhodne datoteke. Nato pa se vloge vhodnih in izhodnih datotek spremenijo. Vhodna datoteka, ki smo jo izčrpali, postane nova izhodna datoteka. Izhodna datoteka na katero smo pisali pa postane vhodna datoteka.

Prednost polifaznega sortiranja pred ostalimi izboljšavami navadnega zlivanja je, da imamo N datotek. Pri uravnoteženem in večsmernem pa jih imamo 2*N. Polifazno sortiranje je algoritem, ki zmanjša število čet na vsakem koraku zanke z zlivanjem čet. Ta algoritem je primeren za urejanje velikih datotek. Z uporabo datotečnih tokov je mogoče urediti datoteke, ki jih ni mogoče naložiti v spomin računalnikov.

Kaj so trakovi in kaj so čete?

• Trak: datoteka kjer so shranjeni podatki, ki jih urejamo
• Četa: četa predstavlja naraščajoče strnjeno podzaporedje danih števil

Poglejmo si na primeru kako se pri zlivanju čet menjajo vloge vhodnih in izhodnih trakov.

Čete imamo že razporejene na štiri trakove. Četrti trak je prazen. To je izhodni trak na katerega bomo pisali. Ostali trakovi so vhodni.
Trak 1: 2 9; 3 6; 4 5 7; 5 6;
Trak 2: 5; 5; 4 5 9;
Trak 3: 4; 7;
Trak 4:--> izhodni trak

Ko zlivamo čete iz prvega, drugega in tretjega traka, jih pišemo na četrti trak. Ker je bilo na tretjem traku najmanj čet, smo ga najprej izpraznili. Tako ta trak postane nov izhodni trak. Na četrtem traku, ki je bil prej izhodni, imamo sedaj zapisane čete, ki jih bomo zlivali naprej. Ta trak je postal vhodni trak.
Trak 1: 4 5 7; 5 6;
Trak 2: 4 5 9;
Trak 3: --> postane izhodni trak
Trak 4: 2 4 5 9; 3 5 6 7; --> postane vhodni trak

Sedaj čete zlivamo na tretji trak (izhodni trak). Najprej smo izpraznili drugi trak, zato postane izhodni trak. Prejšnji izhodni postane vhodni trak.
Trak 1: 5 6;
Trak 2: --> postane izhodni trak
Trak 3: 2 4 4 4 5 5 5 7 9 9; --> postane vhodni trak
Trak 4: 3 5 6 7;

Na vhodnih trakovih imamo povsod zapisano samo še eno četo. Te čete zlijemo in jih zapišemo na izhodni trak.
Trak 1:
Trak 2: 2 3 4 4 4 5 5 5 5 5 6 6 7 7 9 9;
Trak 3:
Trak 4:

Dana imamo števila v poljubnem vrstnem redu. Razdelimo jih na čete. Ena četa predstavlja naraščajoče strnjeno podzaporedje danih števil.

Naredimo tabelo, ki pove koliko čet imamo na določenem traku. Če delamo z tremi traki začnemo tabelo z 100, če delamo z štirimi traki začnemo tabelo z 1000, itd…. Vsaka vrstica predstavlja eno veljavno porazdelitev čet za polifazno zlivanje.

Pri računanju tekoče vrstice upoštevamo vrstico, ki je nad njo. Pri tem pa upoštevamo, da je: a_i-1 = a₁ + a_i, kjer je i = 2,…,n.

Pri tem je po začetni porazdelitvi čet na trakove, zadnji trak vedno prazen.

Števila dobljena v tabeli predstavljajo popolno Fibonaccijevo porazdelitev.

Dobljena tabela nam pove koliko čet imamo na določenem traku. Če imamo v tabeli 3 2 0, pomeni, da so na prvem traku 3 čete, na drugem 2 in na tretjem ni nobene.

Ko imam čete razporejene po trakovih, preverim ali je na zadnjem koraku dovolj čet na vsakem traku. Če teh ni dovolj, dodam ustrezno število navideznih čet na začetek traka.

Kaj je navidezna četa?

To je prazna četa, ki jo, kadar je potrebno, dodajamo na začetek traka.

Nato pa lahko začnem z zlivanjem čet po trakovih. Zlivam na izhodni trak. To je tretji trak, ki je bil do sedaj prazen. Prvo četo na prvem traku zlijem s prvo četo na drugem traku in jo napišem na tretji trak, itd… . Pri zlivanju ene čete z drugo sproti urejam števila v naraščajoči vrstni red. Kjer čete ostanejo jih pustimo na istem traku kot so bile.

Stanje pred zlivanjem:
Trak 1: 1.četa, 3.četa, 4.četa, 6.četa, 7.četa, 9.četa, 10.četa, 12.četa
Trak 2: 2.četa, 5.četa, 8.četa, 11.četa, 13.četa
Trak 3:

1. korak zlivanja:
Trak 1: 9.četa, 10.četa, 12.četa
Trak 2:
Trak 3: 1.četa + 2.četa, 3.četa + 5.četa, 4.četa + 8.četa, 6.četa + 11.četa, 7.četa + 13.četa

2. korak zlivanja:
Trak 1:
Trak 2: 1.četa + 2.četa + 9.četa, 3.četa + 5.četa + 10.četa, 4.četa + 8.četa + 12.četa
Trak 3: 6.četa + 11.četa, 7.četa + 13.četa

3. korak zlivanja:
Trak 1: 1.četa + 2.četa + 9.četa + 6.četa + 11.četa, 3.četa + 5.četa + 10.četa + 7.četa + 13.četa
Trak 2: 4.četa + 8.četa + 12.četa
Trak 3:

Tako zlivanje nadaljujem dokler ne dobim samo ene čete na enem traku. Tako dobim števila urejena v naraščajočem vrstnem redu.

1. Koliko trakov imamo v splošnem pri polifaznem sortiranju? Od tega koliko je izhodnih?

Preveri

2. Kaj je četa?

Preveri

3. Kakšno formulo uporabljamo pri sestavljanju tabele?

Preveri

4. Kaj pomeni, če imamo v tabeli npr. 1 1 0?

Preveri

5. Če na 1. traku manjkata 2 četi, na 2. traku pa 3 čete, kam damo četo najprej? Zakaj?

Preveri

Knjižni viri:

• Boštjan Vilfan: OSNOVNI ALGORITMI, 2. izdaja, izdala Fakulteta za računalništvo in informatiko Ljubljana, 2002.
• Donald E. Knuth: "THE ART OF COMPUTER PROGRAMMING", volume 3, Kanada 2007.

Internetni viri:

• http://www.e-studij.si/Algoritem_za_polifazno_urejanje

• http://www.studenti.pef.upr.si/~matejg/3-letnik/APS-skripta/APS2-Predavanja.pdf

• http://lalg.fri.uni-lj.si/~vilfan/OSNOVNI-ALGORITMI.pdf

• http://colos1.fri.uni-lj.si/ERI/RACUNALNISTVO/OS/naini_dostopa.html

• http://penelope.fmf.uni-lj.si/diri0607/index.php/Doma%C4%8De_naloge_OP_2009_10/5DN/nalogeAlesDrinovec/zlivanje