Innsetningarröðun

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(n²) reiknirit, eins og valröðun og víxlunarröðun. Meðaltími er O(n²) og í besta tilfelli er hann línulegur, O(n).
• Getur raðað lista jafn óðum og stök úr honum berast

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:

1. 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.
2. 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;

Í besta falli er innsetningarröðun O(n), ef listinn sem það fær er þegar raðaður. Þá þarf aðeins að að bera hvert stak í listanum saman við stakið á undan, og sjá þannig að listinn er raðaður. Sams konar inntak væri versta mögulega inntak fyrir snarröðun, þar sem röðun á röðuðum lista er O(n²). Þannig getur það hjálpað okkur ef við vitum að listi er að miklu leyti raðaður, að nota innsetningarröðun í stað snarröðunar.

Í versta falli er reikniritið O(n²), ef listinn er raðaður í öfuga röð. Þá þarf hver innsetning að flytja öll stök raðaða listans til hægri áður en hægt er að stinga inn nýja stakinu. Meðaltími innsetningarröðunar er einnig O(n²), og er hann því sjaldnast hagkvæmur við röðun á stærri listum. Hann er þó eitt af hröðustu röðunarreikniritunum fyrir lista með mjög fá stök, t.d. innan við 10.