Сортування включенням — Вікіпедія

Сортування включенням
	Приклад сортування масиву випадкових чисел.
Клас	Алгоритм сортування
Структура даних	масив
Найгірша швидкодія	О(n2)
Найкраща швидкодія	О(n)
Середня швидкодія	О(n2)
Просторова складність у найгіршому випадку	О(n), O(1)
Оптимальний	Переважно ні

Сортування включенням або сортування вставлянням^[1] — простий алгоритм сортування на основі порівнянь. На великих масивах є значно менш ефективним за такі алгоритми, як швидке сортування, пірамідальне сортування та сортування злиттям. Однак, має цілу низку переваг:

простота у реалізації
ефективний (зазвичай) на маленьких масивах
ефективний при сортуванні масивів, дані в яких вже непогано відсортовані: продуктивність рівна O(n + d), де d — кількість інверсій
на практиці ефективніший за більшість інших квадратичних алгоритмів (O(n²)), як то сортування вибором та сортування бульбашкою: його швидкодія рівна n²/4, і в найкращому випадку є лінійною
є стабільним алгоритмом

Наприклад, більшість людей при сортуванні колоди гральних карт, використовують метод, схожий на алгоритм сортування включенням.

Приклад сортування включенням. Елементи в чорних рамках — посортована частина списку. Метод порівнює наступний елемент непосортованої частини (червона рамка) з послідовними елементами посортованої та вставляє у потрібне місце.

Опис[ред. | ред. код]

На кожному кроці алгоритму ми вибираємо один з елементів вхідних даних і вставляємо його на потрібну позицію у вже відсортованому списку доти, доки набір вхідних даних не буде вичерпано. Метод вибору чергового елементу з початкового масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай (і з метою отримання стійкого алгоритму сортування), елементи вставляються за порядком їх появи у вхідному масиві.

Реалізація[ред. | ред. код]

Pascal

for i := 2 to arrayLength do begin   key := arr[i];   j := i;   while (j > 1) and (arr[j - 1] > key) do 	begin 	  {обмін елементів} 	  tempValue :=  arr[j]; 	  arr[j] := arr[j - 1]; 	  arr[j - 1] := tempValue; 	  j := j - 1; 	end;   arr[j] := key; end;

C++

#include <iostream> #include<ctime> using namespace std; const int Nmax = 100000; void InsertSort(int arr[], int n) {     int key, i;     for (int k = 1; k < n; k++) {         key = arr[k];         i = k - 1;         while ((i >= 0)&&(arr[i]>key)) {             arr[i + 1] = arr[i];             i = i - 1;         }         arr[i + 1] = key;     } } int main() {     int n = 0;     cout << "Rozmir: ";     cin >> n;     int arr[Nmax];     srand(time(NULL));     for (int i = 0; i < n; i++){         arr[i] = rand()% 10;     }     for (int i = 0; i < n; i++){         cout << arr[i] << "  ";     }     cout << endl;     cout << "InsertSort:" << endl;     InsertSort(arr, n);     for (int i = 0; i < n; i++)     {         cout << arr[i] << "  ";     }     cout << endl;     system("pause"); }