Vahelepanemisega sortimine
From Wikipedia, the free encyclopedia
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.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/25/Insertion_sort_animation.gif/220px-Insertion_sort_animation.gif)
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