Vahelepanemisega sortimine

Vahelepanemisega sortimine (inglise insertion sort) on sortimisalgoritm, täpsemalt on tegu võrdlussortimisega, mis ehitatakse ühe sisestuse haaval. Antud sortimine on mõeldud eeskätt viitavale loetelule, kus elemendi lisamiseks tuleb vahetada väiksemalt elemendilt viit endale (ja/või temale) ja luua viit suuremale/võrdsele elemendile (ja/või temalt). Massiivide puhul (kus elemendid ei viita teineteisele) tuleks iga vahelepanemisega palju elemente nihutada ja algoritm oleks ebaefektiivsem.

Vahelepanemisega sortimise keskmine keerukus on Θ(n2/4), mis tähendab, et see on ebaefektiivne suurte andmehulkade korral, kuid omab siiski mitmeid eeliseid:

 Lihtne programmeerida
 Efektiivne (üsna) väikeste andmehulkade puhul
 Efektiivne andmehulkade puhul mis on juba osaliselt sorditud
 Efektiivseim nn. lihtsatest Θ(n2) efektiivsusfaktorit omavatest algoritmidest
 Stabiilne (ei vaheta relatsioonilist järjekorda, mida omavad elemendid võrdsete võtmetega)
 igale-antud-kohale tüüpi algoritm, nõuab fikseeritud suurusega vahemäluala (puhvrit) O(1)
 Online-tüüpi algoritm, sortida saab siis, kui andmeid saadakse

 Algoritm 

 Kustuta elemendi viidad
 Võta järgmine element
 Kustuta järgmise elemendi viidad
 Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele eraldatud elemendiga
 Kustuta järgmise elemendi viidad
 Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele nn. uute sorditud loetellu
 Korda kahte viimast tegevust

 Lahendus C keeles 
void insertSort(int a[], size_t length) {
   int i, j, value;

   for(i = 1; i < length; i++) {
       value = a[i];

       for (j = i - 1; j >= 0 && a[j] > value; j--) {
          a[j + 1] = a[j];
       }

       a[j + 1] = value;
   }
}

 Näited 

Näide, kuidas sortimise algoritm töötab viie elemendi korral (-> sümboliseerib ühepoolset viitamist):

31->25->12->22->11 //kustutan 1 viida
31  25->12->22->11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida
25->31  12->22->11 //kustutan 1 viida, võrdlen 2 korda, loon 1 viida
12->25->31  22->11 //kustutan 1 viida, võrdlen 2 korda, loon 2 viita
12->22->25->31  11 //kustutan 1 viida, võrdlen 4 korda, loon 1 viida  
11->12->22->25->31 
//Θ(n*1,8)

Näide teisele poole sortimisest:

31->25->12->22->11 //kustutan 1 viida
31  25->12->22->11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida
31->25  12->22->11 //kustutan 1 viida, võrdlen 2 korda, loon 1 viida
31->25->12  22->11 //kustutan 1 viida, võrdlen 1 korra, loon 2 viita
31->25->22->12  11 //kustutan 1 viida, võrdlen 1 korra, loon 1 viida  
31->25->22->12->11
//Θ(n)

 Analüüs 

Parimal juhul, kui andmed on juba sorditud, on rakendamisel sortimise efektiivväärtus: Θ(n): iga iteratsiooni (tsükli ületäitumise) korral võrreldakse ainult üks kord (seda viimase elemendiga) ja nõnda kogu andmehulga korral. See on kiirsordi kõige ebameeldivaim juhtum. Kui andmed on peaaegu sorditud, annab algoritm märgatavalt paremaid tulemusi kui kiirsortimine.

Kõige ebameeldivam juhtum oleks, kui andmed oleksid sorditud tagurpidi, kuna iga element peab otsima kõik sorditud andmed läbi, et leida endale koht. Antud juhul oleks algoritmi efektiivsusfaktor Θ(n2), mis veelkord näitab algoritmi ebapraktilisust suurte andmekoguste korral. Siiski on vahelepanemisega sortimise sisemine kordus väga kiire, mis teeb ta üheks kiiremaks sortimisalgoritmiks väheste elementidega (u 10).

Üks universaalne sortimisprotseduur oleks sortida keeruka sortimisalgoritmiga algselt andmed ära ja lõpetada vahelepanemisega sortimisega.

Kategooria:Sortimisalgoritmid

no:Sorteringsalgoritme#Innstikksortering