|
'''Röðunarreiknirit''' 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.
==Flokkun==
Röðunarreiknirit eru flokkuð eftir:
* [[Tímaflækja|Tímaflækju]] samanburða. Þá skipta [[Versta tilfelli|versta]], [[meðaltilfelli|meðaltals-]] og [[besta tilfelli|besta]] tilfelli máli, en þau lýsa hlutfallslegum fjölda samanburða sem gera þarf á stökunum, miðað við stærð listans (''n''). Fyrir dæmigerð röðunarreiknirit er góð hegðun [[Stóra O|O]](''n'' log ''n''), og slæm hegðun er O(''n''<sup>2</sup>). Ákjósanlegasta hegðun er O(''n'').
* Tímaflækju víxlana. Víxlanir geta verið seinlegar í sumum tilfellum.
* [[Vinnsluminni|Minnisnotkun]] (og notkun annara auðlinda). Þá er sérstaklega athugað að sum reiknirit raða „á staðnum“, þannig að þau þurfa lítið aukalegt minni umfram það sem verið er að nota undir listann sem verið er að raða, meðan önnur taka frá aukalegt minni fyrir gögnin þar sem að þau eru geymd tímabundið.
* [[Stöðugleiki röðunarreiknirita|Stöðugleika]]. Röðunarreiknirit kallast ''stöðugt'' ef að það varðveitir afstæða röðun gagna með sams konar lykla.
* Hvort að þau nota samanburðarröðun eða ekki. Samanburðarröðun ber saman gögnin eingöngu með samsemdarvirkja (ekki [[hlutröðunarvensl|hlutröðun]]).
* 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.
==Algeng röðunarreiknirit==
Í þ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.
<!-- I use ·s below to try to keep the column contents from wrapping in an undesirable way while still adjusting to different font sizes. -->
{|class="wikitable"
!Nafn !! Best !! Meðaltal !! Verst !! Minni !! Stöðugt !! Aðferð !! Athugasemdir
|- align="center"
|[[Bóluröðun]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Víxlun
|nowrap align="left"|Bestu tímar eru mismunandi.
|- align="center"
|[[Hristiröðun]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Víxlun
||
|- align="center"
|[[Greiðuröðun]]
|style="background:#ddffdd"|O(''n'' log ''n'')
||—
|style="background:#ddffdd"|O(''n'' log ''n'')
|style="background:#ddffdd"|O(1)
|| Nei
|| Víxlandi
||
|- align="center"
|[[Dvergaröðun]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Víxlun
||
|- align="center"
|[[Valröðun]]
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ddffdd"|O(1)
|| Nei
|| Val
||
|- align="center"
|[[Innsetningarröðun]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Innsetning
||
|- align="center"
|[[Skeljaröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
||—
||O(''n''log<sup>2</sup>(''n''))
|style="background:#ddffdd"|O(1)
|| Nei
|| Innsetning
|nowrap align="left"| Bestu tímar eru breytilegir
|- align="center"
|[[Tvíundartrésröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
||—
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Innsetning
||
|- align="center"
|[[Bókasafnsröðun]]
|style="background:#ddffdd"|O(''n'')
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
||O(''n'')
|style="background:#ddffdd"| Já
|| Innsetning
||
|- align="center"
|[[Sameiningarröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
||—
|style="background:#ddffdd"|O(''n''log(''n''))
||O(''n'')
|style="background:#ddffdd"| Já
|| Sameining
||
|- align="center"
|nowrap|[[Sameiningarröðun]] á staðnum
|style="background:#ddffdd"|O(''n''log(''n''))
||—
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(1)
|style="background:#ddffdd"| Já
|| Sameining
|nowrap align="left"| Bestu tímar eru breytilegir
|- align="center"
|[[Hrúguröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
||—
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(1)
|| Nei
|| Val
||
|- align="center"
|[[Smoothsort]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(1)
|| Nei
|| Val
||
|- align="center"
|[[Snarröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
||O(log ''n'')
|| Nei
|| Sneiðun
|nowrap align="left"| Einföld afbrigði nota O(''n'') minni
|- align="center"
|[[Innhorfsröðun]]
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(''n''log(''n''))
|style="background:#ddffdd"|O(''n''log(''n''))
||O(log''n'')
|| Nei
|| Samsuða
||
|- align="center"
|[[Kapalröðun]]
|style="background:#ddffdd"|O(''n'')
||—
|style="background:#ddffdd"|O(''n''log(''n''))
||O(''n'')
|| Nei
|| Innsetning
|align="left"| Finnur allar lengstu vaxandi hlutrunur á O(''n'' log log(''n''))
|}
Þessi tafla lýsir röðunarreikniritum sem nota ekki samanburðarröðun. Sem slík eru þau ekki takmörkuð af O(''n''log(''n'')) neðri mörkum. Tímaflækjur eru miðuð við ''n'', fjölda staka, og ''k'', stærð hvers staks.
{|class="wikitable"
!Nafn !! Best !! Meðaltal !! Verst !! Minni !! Stöðugt
|- align="center"
|[[Pigeonhole sort]]
|style="background:#ddffdd"|O(''n''+2<sup>''k''</sup>)
||—
|style="background:#ddffdd"|O(''n''+2<sup>''k''</sup>)
||O(2<sup>''k''</sup>)
|style="background:#ddffdd"| Já
|- align="center"
|[[Bucket sort]]
|style="background:#ddffdd"|O(''n'')
|style="background:#ddffdd"|O(''n'')
|style="background:#ffdddd"|O(''n''<sup>2</sup>)
||O(2<sup>''k''</sup>)
|style="background:#ddffdd"| Já
|- align="center"
|[[Counting sort]]
|style="background:#ddffdd"|O(''n''+2<sup>''k''</sup>)
||—
|style="background:#ddffdd"|O(''n''+2<sup>''k''</sup>)
||O(''n''+2<sup>''k''</sup>)
|style="background:#ddffdd"| Já
|- align="center"
|[[Radix sort]]
|style="background:#ddffdd"|O(''n''·2<sup>''k''</sup>)
||—
|style="background:#ddffdd"|O(''n''·2<sup>''k''</sup>)
||O(''n'')
|style="background:#ddffdd"| Já
|}
Þessi tafla lýsir röðunarreikniritum sem eru óraunhæf fyrir raunverulega notkun sökum hrikalegrar tímaflækju eða þarfar á mjög sértækum búnaði.
{|class="wikitable"
!Nafn !! Best !! Meðaltal !! Verst !! Minni !! Stöðugt !! Samanburður !! Athugasemdir
|- align="center"
|[[Bogosort]]
||O(''n'')
|nowrap|O(''n'' × ''n''!)
|nowrap|engin takmörk
||O(1)
|| Nei
|| Já
||
|- align="center"
|[[Stooge sort]]
|nowrap|O(''n''<sup>2.71</sup>)
||—
|nowrap|O(''n''<sup>2.71</sup>)
||O(1)
|| Nei
|| Já
||
|- align="center"
|[[Bead sort]]
||O(''n'')
||—
||O(''n'')
||—
|| Á ekki við
|| Nei
|nowrap align="left"| Þarf sérstakan búnað
|- align="center"
|[[Pancake sorting]]
||O(''n'')
||—
||O(''n'')
||—
|| Nei
|| Já
|nowrap align="left"| Þarf sérstakan búnað
|- align="center"
|[[Sorting network]]s
|nowrap|O(log ''n'')
||—
|nowrap|O(log ''n'')
||—
|| Já
|| Já
|nowrap align="left"| Þarf sérstaka rás af stærð O(''n''log''n'')
|}
===Bóluröðun ===
'''[[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.
===Snarröðun ===
'''[[Snarröðun]]''' (e. ''quicksort'') er svokallað [[deili- og drottnunarreiknirit]] (e. divide and conquer algorithm), það sem það brýtur verkefnið niður í sífellt smærri parta, allt þar til verkefnin verða svo smá í sniðum að auðvelt er að leysa þau. Til að raða [[fylki]] skiptir snarröðun því í tvo hluta með sérstakri [[aðgreiningaraðferð]] eða [[sneiðun]] (e. partition operation).
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 ===
'''[[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===
'''[[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===
'''[[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===
'''[[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 ===
'''[[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]]
[[ar:خوارزميات الترتيب]]
[[ca:Algorisme d'ordenació]]
[[de:Sortierverfahren]]
[[en:Sorting algorithm]]
[[es:Algoritmo de ordenamiento]]
[[fa:الگوریتمهای مرتبسازی]]
[[fi:Lajittelualgoritmi]]
[[fr:Algorithme de tri]]
[[he:מיון (מדעי המחשב)]]
[[it:Algoritmo di ordinamento]]
[[ja:ソート]]
[[ko:정렬 알고리즘]]
[[lt:Rūšiavimo algoritmas]]
[[nl:Sorteeralgoritme]]
[[pl:Sortowanie]]
[[pt:Algoritmo de ordenação]]
[[ru:Алгоритм сортировки]]
[[sv:Sorteringsalgoritm]]
[[th:อัลกอริทึมการเรียงลำดับ]]
[[zh:排序算法]]
| 