Сортиране чрез вмъкване

Сортиране чрез вмъкване (на английски: Insertion sort) е прост сортиращ алгоритъм. Чрез сравняващо сортиране сортираният списък се допълва с по един елемент всеки път. Алгоритъмът е доста неефикасен в сравнение с quicksort, heapsort или mergesort, ако се прилага върху големи списъци, но от друга страна има и доста предимства.

В най-лошия случай алгоритъмът има сложност O(n²)

Принцип на действие

1. Списъкът с елементи, които ще бъдат сортирани се разделя на две части: частта със сортираните елементи и частта с несортираните
2. При всяка стъпка се взема първия елемент от несортирания списък и се вмъква на правилната позиция в сортираната част от списъка
3. Сортирането продължава докато елементите от несортираната част на списъка се изчерпят

Пример

46 60 56 81 16	Взема се първия елемент от несортирания списък (46) и се поставя на правилното място в сортирания.
46 60 56 81 16	Взема се първия елемент от несортирания списък (60) и се поставя на правилното място в сортирания.
46 60 56 81 16	Взема се първия елемент от несортирания списък (56) и се поставя на правилното място в сортирания.
46 56 60 81 16	Взема се първия елемент от несортирания списък (81) и се поставя на правилното място в сортирания.
46 56 60 81 16	Взема се първия елемент от несортирания списък (16) и се поставя на правилното място в сортирания.
16 46 56 60 81	Списъкът е сортиран

Код на C++

#include <iostream>
using namespace std;

int main()
{
        int array[5]={46,60,56,81,16};

        for(int i=1; i<5; i++)
        {
                int index = array[i];
                int dec = i;
                while(dec>0 && array[dec-1]>=index)
                {
                        array[dec]=array[dec-1];
                        --dec;
                }
                array[dec]=index;
        }

        for(int i=0; i<5;i++)
        cout << array[i] << "\t";
        return 0;
}