Vahelepanemisega sortimine

Vahelepanemisega sortimist demonstreeriv animatsioon

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 Θ(n²/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 Θ(n²) 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

1. Kustuta elemendi viidad
2. Võta järgmine element
3. Kustuta järgmise elemendi viidad
4. Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele eraldatud elemendiga
5. Kustuta järgmise elemendi viidad
6. Sobita (lisa ette, vahel või järele) vastavalt sortimisvõtmele nn. uute sorditud loetellu
7. 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 Θ(n²), 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.