56 
Informatica št. 1 letnik 1977 
urejanje zaporedij v. batagelj 
UDK 681.3.06/07 FNT, VTO matematika in mehanika 
LJubljana 
Namen sestavka Je seznaniti bralca z dvema učinkovitima primerjalnima postopkoma za urejanje 
zaporedij znotraj pomnilnika. To sta "heap sort" in "guick sort". Poleg splošnega uvoda v posto­
pke urejanja zaporedij, so podani tudi izpisi ustreznih podprogramov, napisanih v struotranu, in 
časovne značilnosti le-teh pri urejanju slučajno zgeneriranih zaporedij na računalniku Cyber. 
INTERNAL SORTING METHODS - In the paper two efficient internal sorting methods, "heap sort" and 
"quick sbrt", are presented. Their tirne characteristics for sorting random generated data on 
Cyber are also give.n.- ;< 
Imejmo zaporedje n podatkov iz linearno 
urejene množice ( P , .^ ) 
Pl . P2 > Pj •••••« Pn 
Urediti dano zaporedje, pomeni poiskati tako 
permutacijo indeksov jc , da bo zaporedje 
P^(i)' Pjr (2)' P7r(3)' ••• ' Pjr(n) 
urejeno v nepadaJočem vratnem redu; kar pome­
ni, da za vsak par indeksov i in J velja: 
i < J 
Pyi-(i)<:P9r(J) 
Pogosto pri urejanju preuredimo kar samo za­
poredje (permutaeija Je določena implicitno). 
Postopke urejanja zaporedij delimo na 
- zunanje J zaporedje je datoteka na zunanjem 
pomnilniku 
- notranje : zaporedje se v celoti nahaja v 
hitrem pomnilniku. 
Postopke urejanja razvrščamo naprej na 
- postopke, ki upoštevajo notranjo strukturo 
podatkov 
- primerjalne postopke, ki upoštevajo samo 
linearno urejenost množice P 
V tem sestavku se bomo omejili na primerjalne 
postopke urejanja znotraj pomnilnika. Ti pos­
topki se v glavne uporabljajo kot sestavni 
deli drugih postopkov} morda najpogosteje pred 
izpisom podatkov. 
V programih najpogosteje srečujemo takoimenor 
vani "bubble aort" postopek 
k »—n 
for ( i = 1, n-1 ) do 
k •- k - 1 
for ( j = 1, k ) do 
M ( p(j)>p(j+l) ) then 
Jpremenjamo podatka) 
t •—p(j) 
p(j)«-p(j+l) 
p(j+l)»— t 
endif 
endfor 
endfor 
ali njegove inačice oziroma izboljšave (glej 
primer v dodatku). 
Kompleksnost postopkov urejanja je odvisne 
od večih parametrov. Za primerjalne postopke 
je najznačilnejši parameter število primer­
janj. 
Poglejmo kolikšno j6 število primerjanj za 
gornjo verzijo "bubble sort" postopka. Iz 
programa vidimo, da se primerjanje izvrši 
v-t m-l 
i 
i-1 

57 
krat. Torej n(n-l)/2 krat. Izboljšani pro­
gram iz dodatka potrebuje v splošnem manj pri­
merjanj, vendar Je v povprečju še vedno reda 
n . V najslabšem primeru, ko Je zaporedje ure­
jeno v nenaraščaJočem vrstnem redu, pa Je ena­
kovreden gornjemu postopku. 
Postavi se vprašanje:koliko najmanj primerjanj 
Je potrebnih pri urejanju zaporedja n po­
datkov z "najboljšim" primerjalnim postopkom? 
Do odgovora na zastavljeno vprašanje pridemo 
z naslednjim razmislekom. Vse možne izvršitve 
poljubnega primerjalnega postopka, lahko pri­
kažemo z binarnim drevesom, katerega notranje 
točke so primerjanja, končne točke (listi) pa 
permutacije. 
Primer dela mogočega drevesa izvršitve pri 
urejanju zaporedja a,b,c,d Je prikazan na 
sliki. 
Torej Je kompleksnost postopka povezana z 
dolžinami poti po tem drevesu od korena do 
lista. Zato se vprašamo: koliko Je najmanj 
največja dolžina poti po drevesu? Žtevilo 
listov drevesa (permutacij) Je vsaj nJ. Po 
poteh dolžine k lahko pridemo v največ 2 
listov. Torej mora veljati 
2* > nI 
oziroma po Stirlingovem približku 
k > n loggn - n/ln 2 • loggn/ 2 • c 
Torej Je 
opt 
:ij n log2 n 
Od tu vidimo, da Je kompleksnost "najboljših" 
primerjalnih postopkov urejanja zaporedij 
reda n log n. 
Poleg časovne kompleksnosti (število operacij). 
Je pomembna tudi prostorska kompleksnost (zah­
teve po pomnilniku). Najboljši postopki ureja­
nja bodo za urejanje potrebovali le prostor, 
ki ga zaseda zaporedje podatkov (in program), 
di-ugi pa zahtevajo še dodaten prostor za shra­
njevanje pomožnih rezultatov. 
V dodatku sta opisana dva izmed "najboljših" 
postopkov. 
Prvi postopek, ki ga v literaturi srečamo pod 
imenom "heap aort", ima časovno kompleksnost 
(največjo dolžino poti po drevesu) reda 
n log n in ne potrebuje dodatnega prostora. 
Drugi postopek,imenovan "quick sort", pa je 
primer postopka, ki potrebuje še c log n 
dodatnega prostora in ima povprečno časovno 
kompleksnost (povprečna dolžina poti po dreve­
su) reda n log n. 
Poskusi na slučajnih podatkih (za dane progra­
me glej tabelo v dodatku), kažejo, da Je 
"quick sort" (v povprečju) boljši od "heap 
sort-a"; obstajajo pa tudi zaporedja, za kate-
2 
ra je reda n . Zato previdni programerji 
dajejo prednost zanesljivemu "heap sort-u". 
Več o postopkih urejanja zaporedij lahko bra­
lec prebere v knjigah: 
D.E. Knuth: The Art of Computer Programmingj 
vol.5/ sorting and searchlng; 
Addison-Wesley, 1973 
in 
A.V. Aho, .E. Hopcroft, J.D. Ullman: The 
Design and Anal7sis of Computer 
Algorithms; Addison-Wesley, 197*, 

58 
TABELA ; časovne značilnosti za slučajne podatke za Cyber (čas je merjen v sekundah) 
dolžina 
zaporedja 
0 
10 
50 
100 
200 
500 
1000 
2000 
3000 
5000 
10000 
20000 
30000 
100000 
BUBBLE 
meritve 
.001 
,019 
.074 
.27 
1 .8 
7 .2 
28. 
64. 
•'b 
.001 
.018 
.072 
.29 
1.8 
7.2 
29. 
65. 
180. 
720. 
2900. 
6500. 
72000. 
HEAP 
meritve 
.001 
.010 
.023 
.055 
.16 
.36 
.79 
1.25 
2.2 
4.8 
10. 
16. 
''h 
.001 
,010 
.024 
.055 
.16 
.36 
.79 
1.25 
2.2 
4.8 
10. 
16. 
60. 
QUICK 
meritve 
.002 
.008 
.018 
.045 
.14 
.34 
.78 
1.2 
1.7 
4.5 
9.8 
15. 
F 
q 
.001 
.010 
.023 
.052 
.15 
.34 
.74 
1.2 
2.1 
4.5 
9.7 
15. 
56. 
F^ =. 7.2 n^ 10"^ 
D 
"F 5 
h = 3.6 n log n lO" 
F = 3.4 n log^ n 10 
q 2 
8 J B B L' E - Sor?T 
SUBROLITINE S0RT(TA0,LEN6TH) 
INTE3ER fAB ( 1 I 
INTESER BOUND . CHAH6E 
TABELO TAB(»..LEMGTIO UREJAMO TAK^I DA NA KONEC NEUREJENEGA DELA 
TABELE: SPRAVIMO NJEGOV NAJVECJI ELEMENT, TO PONAVLJAMO VSE"DOKLER NI 
TABELA JREJENA. • ' ' 
iND =•• LEi'^eTH 
REPEAT 
NEUREJENI DEL TABELE PREGLEDUJEMO OD ZAČETKA PROTI KONCU, CE TE-
KOCA ZAPOREDNA ELEMENTA NISTA V PRftVtM VRSTNEM PCbU, JO PREMENJAMO 
DlOUNO » IND - T 
IMO . - . 
FOR (I = ItROUriD) 00 ' 
NEXT = I + r • 
IF (TAB(n.GT.TAB(HEXT)) T^EN 
TEKOČA DVOJICA NI V PRAVEM VRSTNEM REDU, ZATO ELEMENTA 
; PREMENJAMO 
CHAN6E a TABU) 
TAB(I) a TAB(NEXT) 
TAB(NEXT) a CHANGE 
ZAPOMNIMO SI INDEKS PREMENE, PU KONČANEM PREGLEDOV,INJU 
DOLOČA iNnEKS ZADNJE PREMENE KONEC NEUREJENEGA DELA TARELE. 
IND = I 
ENDIF 
E^OFOR 
'JNTIU (INO.LE.i) ENDREPEAT 
TABELA JE UKEJENA 
RETU**N 
ENO 

59 
H E A P - SORT 
SUBROUTINE SORTlTAn.LENGTH) 
INTE3ER CHAN6E, FATHER, POOT . ^Ohl 
INTE3ER TAB ( 1 ) 
DATA hOOT / 1 / 
• 
• NAD TAPELO TAB(I..LEMGTHI RAZPNEMO BINARNO DREVOI TAKO DA VELJA« 
• nooT =1 IN ZA POLJUBNO TOCKO NOOE « FATHER • ENiiERiNOrE/?) • 
• LEFTSON B 3»N0De TER RIOHTSON » L^fTSON • f , 0REV0» V KATEREM JE 
» VRH VSAKEGA PODOrtEVES; VECJI 00 VSE" SVOJIH NASLEDNIKOV IMENUJEMO 
• KOPICA (MEA''). TABELO TAR UREJAMO T^KO, DA NAJPREJ SESTAVIMO IZ 
• NJE KOPICO. NA VRH') KOPICE JE NAJVEČJI tLEMENT lABEtE. ODSTRANIMO GA, 
• PREOSTALE EI-EMENTE ZOPET PReU»EDIMO"V KOHIcO. TO PONAVLJAMO VSEDOKLER 
• NI TABELA UREJENA. 
» 
• SESTAVIMO KOPICO 
roR (NODE a 2»LENGTM) DO 
» 
» PREO'»OSTAVIMOI-DA JE TABti..N0DE-,-) KOPICA. PREOELAJMO V KOPICO 
• TABU..NODE) » TAKO DA POHAKNEMO ELEMENT TAB<N00E) NAVZGOR NA 
» NJEGOVO MESTO V HIERARHIJI. 
« 
SON B NOnE 
REPEAT 
FATHER = SOfi/? 
IF (TAB(FATMER).0E.TA3(S0NM EAIT 
» 
• POMAKNEMO SE NAVZOOR 
• 
CHAN6E s TAe(FATHEP) 
TAB(FATHEf>) = TAB(SON) 
TAbISON) a CHANGE 
SON a FATHFR 
U^JTIL (SON.LE.ROOT) ENOREPEAT 
ENOFOR 
• 
» UREDIMO TABELO 
» • .. • 
NODE •» LENGTH 
1.00P 
o 
• PREllENJAMO TAB(NOOE) 1*1 T,,a(R00T) . DEL TABEUE TAB(NOOE.. 
• LENGTH* JE TAKO UREJEN. 
CHANoe = TARdlODEl 
T^B(NOOE) = TAf((ROOT) 
TA8(R00T) = CH,.MGE 
» 
• . ELEMENT TABJHOOT) POMAKNEJO PO DELO TABELE TAB{i,,NOOE-l) 
• PRIPADAJOČEM OREVESU NAVZpOLt TA^O DA ZASEDC V HIERARHIJI 
• PRIPADAJOČE MU MESTO. DEL TABELE TAbI1..NODE-1) 'JE POSTAL 
• KOPICA. 
« 
:J00E " NODE - r 
iFi (NOOE.LE.HOOT) RETURN 
FATHER = ROOT 
LOOP 
SON 3 2»FflTHER 
IF (SON.GT.fjOOEI EXIT 
• OJLOclHO VEČJEGA OD BPATOV 
» 
IF <(TAbtS0M).LT.TA8<S0N*i> »,ANO,<SON.LT.rjODE)) SON • SON^i 
IF <TAB<FATH£P).GE.TArt(SON() EAIT 
• POMAKNEMO SE NAVZOOL 
CHAN6E = TAB(FATHER) 
TAb(FATHER) =1 TAB(SON) 
TAH(SON) S: CHANGE 
FATHER = SON 
E^JDLOOP 
ENOLOOP 
« 
ENO 

60 
Q J- I C K - SORT 
SUBROUTINE S0RT(TAn,UEN6TH) 
INTESER CHANliC. DELTA , DEPTH i HIOHT 
INTEŠER TA8 (T ), STACK ( 3 ) 
• " • 
• TABELO TAn(i..LEMGTH) UREJAMO TAK", OA JO GLEDE TJA IZBRANI ocLiLMr 
• ELEMENT RAZaiJEMO NA DVA OELA« PRI CEMEK OELILMI ELEMENT ZASEOE SVOJE 
• MESTO V UREJENI TABELI IN JE VsAK ELEMENT PRVEGA DELA MANJST00 VSA-
<» KESA ELEMENlA IZ DRUGEGA DELA. ZA V^AK UEL P0SE8EJ. CE NI UPCjEN, P0--
• STOPEK PONOVIMO, TADELA JE UPE.JENA. KO SO UREJENI vsi DOBLJENI DELI. 
tt • -.. . 
nEPTH; = ,.. OLDBINA LASTNEGA SKLADA 
LEPT = j ,,, SPODUJI iNOtKS DELA TABELE« KI GA UREJAMO 
RIGMT 3 LENGTM ... Z(5uRUJI iNOtKS DELA TABELE« KI 6A UREJAHO 
tOOP 
« 
• CE^ TEKOcI DEL TABELE SE NI UREJE^^« GA RAZBIJEMO IN NADALJUJEMO Z 
•> UPEJENJEi^l KRAJSEGA DELA. DAl.JSI iJEu Sl ZAPOHNIHOV DRUGAČE NAOALJU-
» jEMO Z UHEjANJEM ENEGA iZMEo PREOSTALIH NEUREJENIH DELOV J CE NI 
» NOBENEGA VEC, JE TAOELA UREJEl-lA. 
» 
DELTA = RIGHT - LEFT 
IF; (OELTA.GT.i) THEN 
» TEKOci DEL TABELE VSEPUJE VEC KOT ? ELEMENTA, DELITCV NADAT 
• LJUJEflO. SIRSI DEL TABELE SI ;«AP0MNIH0 (MgjI SPRAVIRO W S^LAO) 
» • • • • . 
CALL SPLIT (T/>n.LEFT.RT5HT,NLEFT,NRIGHT) 
IF (NLEFT.LT.NRIGHT) THfN 
DEPTH a nEPTH + r 
STACK(OEPTH-l) = NuEFT 
STACK(0£PTH) a NRIGHT 
ENDIF 
ELSE 
» TEKOČI DEL TABELE VSERDJE NAJVEC Ž ELEMENTA, CE STA Z, 
» J'J. CE JE POTRECNO. UREDIMO. 
o 
IF ((OELTA.EO.l),AND.(TAB<LEFT>.eT.TAB(HIGHT))) ThEN 
CHANGE a TAD(LeFT) 
TAB(LEFT) » TAB(RIGHT) 
TAB(ftlGHT) = CHANGE 
EtJUlF 
« 
• PRIPRAVIMO NOV DEL TABELE (MEJI ViAMEMo Z VRHA SKLADA)» CE QA 
» NI KONČAMO 
« 
IF (DEPTH LE.') RETURN 
LEI^T = STACK (OEPTli-1) 
RKiHT = STACK(DEPTII) 
DEHTri = DEPTH - ? 
ENDIF 
ENDLOOP 
ENO 

61 
- "•- SUBROUTiNE ŠPLiTITADiLEiFt.RIGHT.NLEFT.NRIOHT) -:.--_... 
T : -INTE3ER fAB:'= .( 1 r?-' 
-"•" INTEŠER-ČHANOE. ČUT "'.-RIGHT'. MSCAN • TEHP • 
spiiiT'j£iPoMOZNA""RUTifiA' PODPROGRAMA (OUICK)SORT. DEL TABELE ^ --
TAB(L£FT..RlGHT)-.RAZniJE^:NA-OALJSI OEL TAB(NLEKT..NRieHT) IN .3;: 
KRAJŠI 0EL''TAB<1^'EFT..RIOHT)-. 
DEL TABELE -T AB(LEFT,.RIGHf)" PREUREDIMO TAKO. DA SO NA LEVi STRAfir 
DELILNESA ELEMENTA VSI (00 NJEGA) MANjSil NA DESNI PA VSTVECJI ALI 
ENAKI ELEMENTI. S TEH OELiLNi ELEMENT ZASEOE MESTO, Kl GA ZASEDA V -
UREJENI TABtLIi'' ,:•/:-•• -' ;"o 
CUT := (LEFT +- RlGHTlV? 
TEMP = TABtCUT) ' .;. 
RSCA^. -.HIGHT, ... 
LSCA^" •=• LEFT-^ • ..-i 
DELILNI ELEMENT 
ZGORNJI INDEKS SE NEP«EUHEJENEGA OELA 
SPODNJI INDEKS SE NEP^EUREJENEGA DELA 
TABFLO PREUHEJAMO TAKO, oi^ POIŠČEMO PRVI ELEMENT 2 LEVE. KI JE VECJI. 
IN PRVi- ELEMENT Z. OESNE. KI JE MANJSI OU DELILNEGA. ELEMENT;, PREHE-. 
NJAMO. TO PONAVLJAMO VSt DOKLER-OBSIAJA NEPREUREJEN.I DEL TABELE. 
• •; (_oop •• • -•^---
: .WHiILE (TAB(LSCAN).LT.TEMP) DO 
LSCAN-' -=-LSCAN +1 --.-..-. 
ENOWHlLE: - ^ 
- - V.'HILE (TAB'RSCAfl) .GT.TEMP) 00 
•.:,'•--' ' RSCAN S-= RSCAM - T 
'• E'JOWHlLE'' • .' -.-.•....--
= • DODILII Š"0 DVA ELEMENTA. KI STOJITA NA NAPACNI SJRANI DELILNEGA 
ELEMENTA. PREMENJAMO JU. 
iFi (LSCAN.eT.RSCAN) EXIT 
CrtANGE 
: TAB(RSCAN> 
- TAB(LSCAN) 
•RSCAN 
• •• 'LSCAN " 
-ENOLOOP- -
= TAE3(RSCA'I) 
TABILSCAM) 
ČnAriGE 
RSCAN -
LSCAN • 
DOLOČIMO NOVA^DELA- TABELA.;>';•'v^^"-
IF ( (LEFT+RlOHT) ,LT..(L;SCAH*RSCAN)) T«EN 
LEVI DEL' JE VECJI 
NLEFT = LEFT 
(JRIGHT = RSCMJ 
LEFT = LSCAN 
ELSE 
DESMI DEL JE VECJI 
NLEFT a LSCAN 
tJi^IGHT a RIGHT 
RIGHT a RSCAN 
ENOIF 
RETU^N 
END