Сортування включенням

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

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

Сортування включенням

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

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

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

Опис

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

Реалізація

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");
}

Див. також

• Список алгоритмів

Джерела

• Кормен, Томас; Лейзерсон, Чарльз; Рівест, Рональд; Стайн, Кліфорд (2019). Розділ 2.1: Сортування вставлянням. Вступ до алгоритмів (вид. 3). К.І.С. с. 35—41. ISBN 978-617-684-239-2. {{cite book}}: Cite має пустий невідомий параметр: |1= (довідка)

Посилання

• Animated Sorting Algorithms: Insertion Sort — графічна демонстрація роботи алгоритму
• Category: Insertion Sort — LiteratePrograms — приклади реалізації алгоритму на різних мовах програмування.
• InsertionSort
• Insertion Sort Demonstration
• Sorting Algorithms Demo
• Сортування включенням