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 
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ðanir eru til dæmis bóluröðun og snarröðun. Valraðanir 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.

Nafn   Best  Meðaltal  Verst  Minni  Stöðugt  Aðferð  AthugasemdirVíxlunarröðunO(n)—O(n2)O(1) Já VíxlunBestu tímar eru mismunandi.HristiröðunO(n)—O(n2)O(1) Já Víxlun GreiðuröðunO(n log n)—O(n log n)O(1) Nei Víxlandi DvergaröðunO(n)—O(n2)O(1) Já Víxlun ValröðunO(n2)O(n2)O(n2)O(1) Nei  Val  InnsetningarröðunO(n)—O(n2)O(1) Já  Innsetning  SkeljaröðunO(nlog(n))—O(nlog2(n))O(1) Nei  Innsetning Bestu tímar eru breytilegirTvíundartrésröðunO(nlog(n))—O(nlog(n))O(1) Já  Innsetning  BókasafnsröðunO(n)O(nlog(n))O(n2)O(n) Já Innsetning  SameiningarröðunO(nlog(n))—O(nlog(n))O(n) Já  Sameining Sameiningarröðun á staðnumO(nlog(n))—O(nlog(n))O(1) Já  Sameining Bestu tímar eru breytilegirHrúguröðunO(nlog(n))—O(nlog(n))O(1) Nei  Val  SmoothsortO(n)—O(nlog(n))O(1) Nei  Val  SnarröðunO(nlog(n))O(nlog(n))O(n2)O(log n) Nei  Sneiðun Einföld afbrigði nota O(n) minniInnhorfsröðunO(nlog(n))O(nlog(n))O(nlog(n))O(logn) Nei Samsuða KapalröðunO(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öðugtPigeonhole sortO(n+2k)—O(n+2k)O(2k) JáBucket sortO(n)O(n)O(n2)O(2k) JáCounting sortO(n+2k)—O(n+2k)O(n+2k) Já Radix sortO(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  AthugasemdirBogosortO(n)O(n × n!)engin takmörkO(1) Nei  Já  Stooge sortO(n2.71)—O(n2.71)O(1) Nei  Já Bead sortO(n)—O(n)— Á ekki við  Nei Þarf sérstakan búnaðPancake sortingO(n)—O(n)— Nei Já Þarf sérstakan búnaðSorting networksO(log n)—O(log n)— Já Já Þarf sérstaka rás af stærð O(nlogn)

 Víxlunarröðun 
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 
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 
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 
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 
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 þessara 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 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 
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ð.

Röðunarreiknirit