Röðunarreiknirit
Röðunarreiknirit eða röðunaralgrím eru aðferðir til að raða stökum í tiltekna röð, til dæmis frá því minnsta til hins stærsta, eða frá því stærsta til hins minnsta.
Flokkun[breyta | breyta frumkóða]
Röðunarreiknirit eru flokkuð eftir:
- Tímaflækju samanburða. Þá skipta versta, meðaltals- og 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 O(n log n), og slæm hegðun er O(n2). Ákjósanlegasta hegðun er O(n).
- Tímaflækju víxlana. Víxlanir geta verið seinlegar í sumum tilfellum.
- Minnisnotkun (og notkun annarra 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öð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öð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[breyta | breyta frumkóða]
Í þ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.
| Nafn | Best | Meðaltal | Verst | Minni | Stöðugt | Aðferð | Athugasemdir |
|---|---|---|---|---|---|---|---|
| Víxlunarröðun | O(n) | — | O(n2) | O(1) | Já | Víxlun | Bestu tímar eru mismunandi. |
| Hristiröðun | O(n) | — | O(n2) | O(1) | Já | Víxlun | |
| Greiðuröðun | O(n log n) | — | O(n log n) | O(1) | Nei | Víxlandi | |
| Dvergaröðun | O(n) | — | O(n2) | O(1) | Já | Víxlun | |
| Valröðun | O(n2) | O(n2) | O(n2) | O(1) | Nei | Val | |
| Innsetningarröðun | O(n) | — | O(n2) | O(1) | Já | Innsetning | |
| Skeljaröðun | O(nlog(n)) | — | O(nlog2(n)) | O(1) | Nei | Innsetning | Bestu tímar eru breytilegir |
| Tvíundartrésröðun | O(nlog(n)) | — | O(nlog(n)) | O(1) | Já | Innsetning | |
| Bókasafnsröðun | O(n) | O(nlog(n)) | O(n2) | O(n) | Já | Innsetning | |
| Sameiningarröðun | O(nlog(n)) | — | O(nlog(n)) | O(n) | Já | Sameining | |
| Sameiningarröðun á staðnum | O(nlog(n)) | — | O(nlog(n)) | O(1) | Já | Sameining | Bestu tímar eru breytilegir |
| Hrúguröðun | O(nlog(n)) | — | O(nlog(n)) | O(1) | Nei | Val | |
| Smoothsort | O(n) | — | O(nlog(n)) | O(1) | Nei | Val | |
| Snarröðun | O(nlog(n)) | O(nlog(n)) | O(n2) | O(log n) | Nei | Sneiðun | Einföld afbrigði nota O(n) minni |
| Innhorfsröðun | O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(logn) | Nei | Samsuða | |
| Kapalröðun | O(n) | — | O(nlog(n)) | O(n) | Nei | Innsetning | 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(nlog(n)) neðri mörkum. Tímaflækjur eru miðuð við n, fjölda staka, og k, stærð hvers staks.
| Nafn | Best | Meðaltal | Verst | Minni | Stöðugt |
|---|---|---|---|---|---|
| Pigeonhole sort | O(n+2k) | — | O(n+2k) | O(2k) | Já |
| Bucket sort | O(n) | O(n) | O(n2) | O(2k) | Já |
| Counting sort | O(n+2k) | — | O(n+2k) | O(n+2k) | Já |
| Radix sort | O(n·2k) | — | O(n·2k) | O(n) | 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.
| Nafn | Best | Meðaltal | Verst | Minni | Stöðugt | Samanburður | Athugasemdir |
|---|---|---|---|---|---|---|---|
| Bogosort | O(n) | O(n × n!) | engin takmörk | O(1) | Nei | Já | |
| Stooge sort | O(n2.71) | — | O(n2.71) | O(1) | Nei | Já | |
| Bead sort | O(n) | — | O(n) | — | Á ekki við | Nei | Þarf sérstakan búnað |
| Pancake sorting | O(n) | — | O(n) | — | Nei | Já | Þarf sérstakan búnað |
| Sorting networks | O(log n) | — | O(log n) | — | Já | Já | Þarf sérstaka rás af stærð O(nlogn) |
Víxlunarröðun[breyta | breyta frumkóða]
Víxlunarröð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[breyta | breyta frumkóða]
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öð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[breyta | breyta frumkóða]
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 sem er tvíundartré þar sem foreldri er ávallt stærra en börnin.
Þegar gögn hafa verið gerð að hrúgu þá er rótin í trénu ávallt stærsta (eða minnsta) stakið af öllum.
Innsetningarröðun[breyta | breyta frumkóða]
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 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[breyta | breyta frumkóða]
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[breyta | breyta frumkóða]
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 fylkisins 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[breyta | breyta frumkóða]
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úgu sem gagnagrind. Þannig verður auðveldara að finna og fjarlægja minnsta (eða stærsta) stakið.