„Röðunarreiknirit“: Munur á milli breytinga

'''Röðunarreiknirit''' eða '''röðunaralgrím''' eru aðferðir til að raða [[stak|stökum]] í tiltekna röð, til dæmis frá því minnsta til hins stærsta, eða frá því stærsta til hins minnsta.

 

Röðunarreiknirit eru flokkuð eftir:

 

* Almennri aðferð: Innsetningu, víxlun, valröðun, sameiningu, o.s.frv. Víxlraðannir eru til dæmis bóluröðun og snarröðun. Valraðannir eru til dæmis hrúguröðun og hristiröðun.

 

Í þessari töflu er ''n'' fjöldi færslna sem á að raða og ''k'' er fjöldi aðgreinanlegra færslna (þ.e., eftir að endurteknar færslur hafa verið fjarlægðar). Dálkarnir „best“, „meðaltal“ og „verst“ gefa tímaflækju hverju sinni. Þar sem að ''k'' er ekki notað er álitið að ''k'' sé fasti. „Minni“ gefur til kynna hversu mikið aukalegt minni þarf umfram það sem listinn tekur.

 

|[[Bóluröðun]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ffdddd"|O(''n''²)

|style="background:#ddffdd"|O(1)

|[[Hristiröðun]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ffdddd"|O(''n''²)

|style="background:#ddffdd"|O(1)

|[[Greiðuröðun]]

|style="background:#ddffdd"|O(''n'' log ''n'')

|style="background:#ddffdd"|O(''n'' log ''n'')

|style="background:#ddffdd"|O(1)

|[[Dvergaröðun]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ffdddd"|O(''n''²)

|style="background:#ddffdd"|O(1)

|[[Innsetningarröðun]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ffdddd"|O(''n''²)

|style="background:#ddffdd"|O(1)

|[[Skeljaröðun]]

|style="background:#ddffdd"|O(''n''log(''n''))

||O(''n''log²(''n''))

|style="background:#ddffdd"|O(1)

|[[Tvíundartrésröðun]]

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(1)

|[[Sameiningarröðun]]

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(''n''log(''n''))

||O(''n'')

|nowrap|[[Sameiningarröðun]] á staðnum

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(1)

|[[Hrúguröðun]]

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(1)

|[[Smoothsort]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ddffdd"|O(''n''log(''n''))

|style="background:#ddffdd"|O(1)

|[[Kapalröðun]]

|style="background:#ddffdd"|O(''n'')

|style="background:#ddffdd"|O(''n''log(''n''))

||O(''n'')

|[[Pigeonhole sort]]

|style="background:#ddffdd"|O(''n''+2^''k'')

|style="background:#ddffdd"|O(''n''+2^''k'')

||O(2^''k'')

|[[Counting sort]]

|style="background:#ddffdd"|O(''n''+2^''k'')

|style="background:#ddffdd"|O(''n''+2^''k'')

||O(''n''+2^''k'')

|[[Radix sort]]

|style="background:#ddffdd"|O(''n''·2^''k'')

|style="background:#ddffdd"|O(''n''·2^''k'')

||O(''n'')

|[[Bogosort]]

||O(''n'')

|nowrap|engin takmörk

||O(1)

|[[Stooge sort]]

|nowrap|O(''n''^2.71)

|nowrap|O(''n''^2.71)

||O(1)

|[[Bead sort]]

||O(''n'')

||O(''n'')

|| Á ekki við

|| Nei

|[[Pancake sorting]]

||O(''n'')

||O(''n'')

|| Nei

|| Já

|[[Sorting network]]s

|nowrap|O(log ''n'')

|nowrap|O(log ''n'')

|| Já

|| Já

|}

 

'''[[Bóluröðun]]''' (e. ''bubble sort'') er einföld aðferð til þess að raða gögnum. Reikniritið byrjar í byrjun gagnanna. Það ber saman fyrstu tvö stökin, og ef að fyrra stakið er stærra en hið síðara, þá víxlar það þeim. Þessi aðgerð er endurtekin fyrir hvert einasta par, uns að endanum er komið. Þá er byrjað upp á nýtt, og það sama gert þar til að engin víxlun fer fram í heila umferð. Í versta tilfelli er ítrað jafn oft og stökin eru. Þrátt fyrir einfaldleikann er þetta reiknirit mjög seinvirkt, og það er sjaldan notað nema í kennslu. Ögn betra afbrigði, ''[[hristiröðun]]'', gengur fram og til baka í stað þess að fara alltaf áfram.

 

 

Til að skipta fylki er valið svokallað [[skiptistak]] (e. pivot). Öll stök sem eru minni en skiptistakið eru sett framan við það, og öll stök sem eru stærri en skiptistakið eru sett aftan við það. Skiptistakið er þá komið á sinn rétta stað í fylkinu. Síðan er [[endurkvæmni]] notuð til að raða þessum tveimur undirfylkjum með nákvæmlega sömu aðferð. Þetta er endurtekið allt þar til undirfylkin eru orðin svo lítil að þau innihalda aðeins eitt stak. Að sjálfsögðu má þá líta á þau sem röðuð.

Snarröðun er, eins og nafnið bendir til, yfirleitt mjög hraðvirk, en erfitt er að útfæra hana þannig að hún verði [[stöðugt röðunarreiknirit|stöðug]]. Hraði snarröðunar fer þó að miklu leyti eftir því hversu vel tekst að velja gott skiptistak. Bestu skiptistökin skipta fylki í tvo svo til jafna hluta.

 

'''[[Hrúguröðun]]''' (e. ''heapsort'') er eins konar [[valröðun]]. Þessi röðun ákvarðar stæsta (eða minnsta) stak og raðar því aftast (eða fremst) í lista. Önnur stök fylgja síðan þessu valda staki. [[Valröðun]] keyrir á O(n^2) hraða en [[hrúguröðun]] vinnur mun hraðar með því að nota [[gagnagrind]] sem kallast [[hrúga (tölvunarfræði)|hrúga]] sem er [[tvíundartré]] þar sem [[foreldri (tölvunarfræði)|foreldri]] er ávallt stærra en [[börn (tölvunarfræði)|börnin]].

 

Þegar gögn hafa verið gerð að [[hrúga (tölvunarfræði)|hrúgu]] þá er rótin í [[tré (tölvunarfræði)|trénu]] ávallt stærsta (eða minnsta) stakið af öllum.

 

'''[[Innsetningarröðun]]''' (e. ''insertion sort'') er einfalt reiknirit sem virkar nokkuð vel þegar raða á tiltölulega smáum lista af stökum, sérstaklega þegar listinn er þegar í næstum réttri röð. Innsetningarröðun er líka oft notuð sem hluti af betri röðunaraðferðum, svo sem [[snarröðun]].

 

Innsetningarröðun gengur þannig fyrir sig að farið er í gegnum hvert stak listans, eitt í einu, og það sett á réttan stað í nýjum röðuðum lista. Þegar innsetningarröðun er notuð á [[fylki (tölvunarfræði)|fylki]] getur nýi raðaði listinn verið hluti af sama fylki og hinn upphaflegi. Aftur á móti getur þetta verið tímafrekt, þar sem rýma þarf fyrir nýja stakinu með því að færa öll stökin sem á eftir því koma um eitt sæti. [[Skeljaröðun]] (sjá hér fyrir neðan) er önnur útgáfa af innsetningarröðun sem virkar betur en venjuleg innsetningarröðun til að raða stórum gagnasöfnum.

 

'''[[Sameiningarröðun]]''' (e. ''mergesort'') nýtir þann eiginleika hversu auðvelt það er að sameina tvo raðaða lista. Röðunin byrjar á að bera saman fyrstu tvö stökin í hvorum lista fyrir sig og afritar minna stakið (eða stærra ef raða á stærsta stakinu fyrst) í nýjan lista. Heldur síðan áfram og ber þá fyrsta stakið í listanum sem var með hærra stak í fyrsta samanburðinum við annað stakið í seinni listanum.

 

Röðunaraðferðin býr til þessa tvo röðuðu lista með því að skipta upprunalega listanum sem á að raða í tvennt, síðan hvorum þessarra nýju lista í tvennt aftur og svo framvegis þangað búið er að búta upprunalega listann niður í lista sem einungis geyma eitt stak hver. Að því loknu eru þessir einingalistar sameinaðir tveir og tveir í einu og mynda þá raðaðan lista með tveimur stökum. Því næst eru þeir listar sameinaðir og svo framvegis þangað til allir undirlistar hafa verið sameinaðir í heilan fullraðaðan lista.

 

'''[[Skeljaröðun]]''' (e. ''Shell sort'') var fundin upp af Donald Shell árið [[1959]]. Hún bætir [[bóluröðun]] og [[innsetningarröðun]] með því að færa stökin sem raða á í stærri skrefum en fyrrnefndar aðferðir. Ein útfærsla á skeljaröðun er þannig að gögnunum er raðað í [[tvívítt fylki]]. Síðan er hverjum dálki [[fylki]]sins raðað með innsetningarröðun. Þessi aðferð er heldur hæg fyrir stór gagnasöfn, en er ein hraðvirkasta aðferðin til að raða litlum gagnasöfnum (með 1000 stök eða færri, um það bil). Annar kostur við skeljaröðun er að hún þarf tiltölulega lítið minnispláss.

 

'''[[Valröðun]]''' (e. ''selection sort'') virkar þannig að fundið er minnsta stakið í lista (eða stærsta, allt eftir því hvort raða á frá minnsta til stærsta, eða frá stærsta til minnsta). Síðan er skipt á því og fyrsta staki listans. Þetta er svo endurtekið fyrir afganginn af listanum (fremsta stakinu, sem nú er raðað, er sleppt).

 

[[Hrúguröðun]] (sjá fyrir ofan) bætir valröðun umtalsvert með því að nota [[hrúga (tölvunarfræði)|hrúgu]] sem [[gagnagrind]]. Þannig verður auðveldara að finna og fjarlægja minnsta (eða stærsta) stakið.

[[Flokkur:Röðunarreiknirit|Röðunarreiknirit]]

 

[[lb:Zortéieralgorithmus]]

[[lt:Rikiavimo algoritmas]]

[[nl:Sorteeralgoritme]]

[[no:Sorteringsalgoritme]]