Innsetningarröðun
From Wikipedia, the free encyclopedia
Innsetningarröðun er einfalt röðunarreiknirit, sem ber saman óröðuð stök, og byggir raðaðan lista eitt stak í einu. Hann er mun óhagkvæmari en til dæmis snarröðun og hrúguröðun þegar raða á stórum listum, en hefur þó ýmsa kosti.
- Einfaldur í útfærslu
- Hagkvæmur þegar raða á litlum listum
- Einnig hagkvæmur á lista sem er að hluta til raðað
- Tekur alltaf jafn mikið minni, O(1)
- Er hagkvæmari en flest önnur einföld O(n2) reiknirit, eins og valröðun og víxlunarröðun. Meðaltími er O(n2) og í besta tilfelli er hann línulegur, O(n).
- Getur raðað lista jafn óðum og stök úr honum berast
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Insertion_sort_animation.gif/220px-Insertion_sort_animation.gif)
Hægt er að hugsa sér virkni innsetningarröðunar þannig að við hverja ítrun sé eitt stak fjarlægt úr inntaklista, og því stungið inn á réttan stað í raðað úttakslista. Þetta er gert þar til engin stök eru eftir í inntakslistanum, en þá er úttakslistanum skilað. Ekki skiptir máli í hvaða röð stökin í inntakslistanum eru valin.
Venjulega er röðunin útfærð þannig að aðeins sé unnið á inntakslistanum, en ekki raðað inn í sérstakan úttakslista. Þá má hugsa sér að eftir k ítranir, innihaldi listinn k fyrstu stök listans röðuð, en stök k+1 til n eru óröðuð (ef listinn er n-stök að lengd). Í hverju skrefi er síðan stak k+1 tekið, og stungið inn á réttan stað í listann, og hin ímynduðu skil í listanum á milli þess raðaða og óraðaða færast fram:
verður:
en þá eru öll stök > x flutt til hægri þegar þau eru borin saman við x.
Algengustu útgáfunni, sem vinnur á fylkjum, má lýsa á eftirfarandi hátt:
- Gefum okkur fallið insert, sem getur stungið stökum inn í raðaðan lista fremst fylki. Það vinnur með því að byrja aftast á raðaða listanum, sem er hluti af fylkinu, og færir hvert stak um eitt sæti til hægri þangað til rétt sæti finnst fyrir nýja stakið. Sem aukaverkun, þá yfirskrifast það stak sem verið var að raða á sínum upprunalega stað, með aftasta stakinu í raðaða listanum.
- Til þess að framkvæma röðun, byrjum við á vinstri enda fylkisins, og köllum á insert fallið, og svo koll af kolli þar til fylkið er raðað.
Hér má sjá einfaldan sauðakóða sem sýnir þessa aðferð útfærða:
insert(array a, int length, value) { int i = length - 1; while (i >= 0 && a[i] > value) { a[i + 1] = a[i]; i = i - 1; } a[i + 1] := value; } insertionSort(array a, int length) { int i = 0; while (i < length) { insert(a, i, a[i]); i = i + 1; } }
Einnig getur verið áhugavert að sjá útfærslu í fallaforritunarmáli eins og Standard ML
fun insertsort [] = [] | insertsort (x::xs) = let fun insert (x:real, []) = [x] | insert (x:real, y::ys) = if x<=y then x::y::ys else y::insert(x, ys) in insert(x, insertsort xs) end;