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

Сортиране чрез вмъкване (на английски: 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;
}

Примерен Код на C#

static int[] InsSort(int[] arr)
{
 for (int i = 0; i < arr.Length; i++)
 {
 int value = arr[i];
 int index = i;
 while (index > 0 && arr[index - 1] >= value)
 {
 arr[index] = arr[index - 1];
 index--;
 }
 arr[index] = value;
 }
 return arr;
}

Примерен Код на Java

public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int next = array[i];
int j = i;
while (j > 0 && array[j – 1] > next) {
array[j] = array[j – 1];
j--;
}
array[j] = next;
}
}

Най-добър, най-лош и среден случай

Анимация на сортиране чрез вмъкване. Сортиране на 30 елемента

В най-добрия случай масивът е почти сортиран. Тогава за сортирането чрез вмъкване е нужно линейно време (т.е. O(n))). При всяка стъпка елементът, който е на ход, се сравнява с най-десния елемент от сортирания масив.

Пример за най-лош случай е когато масивът е напълно обърнат на обратно. Тоест подредбата на елементите ще бъде такава, че всеки следващ елемент ще бъде по-малък от предходния. При тази подредба всяка стъпка във вътрешния цикъл ще се изпълни максимален брой пъти. Това дава на сортирането чрез вмъкване квадратично време за изпълнение (т.е. O(n²)).

Средният случай също е за квадратично време, което прави сортирането чрез вмъкване непрактичен за големи масиви.

Този алгоритъм е един от най-бързите алгоритми за сортиране на малки масиви, дори е по-бърз и от бързо сортиране (QuickSort).

Сравнение с другите алгоритми

Сортиране чрез вмъкване е алгоритъм, много близък до сортиране чрез пряка селекция. В сортиране чрез селекция, след N преминавания през масива, първите N елемента са сортирани. В сортиране чрез селекция това са първите N най-малки елемента, докато при сортиране чрез вмъкване това са N елемента сортирани, но може и да не са най-малките спрямо целия масив. Предимството му пред сортиране чрез селекция е, че са нужни N на брой стъпки за обхождане, където N е текущият елемент, до който сме стигнали, докато в сортирането чрез селекция е нужно абсолютно винаги да се обхожда целият масив.