Сортування вставкою
Матеріал з Вікіпедії — вільної енциклопедії.
Сортування вставкою — простий алгоритм впорядкування даних в лінійному масиві. Основна ідея алгоритма полягає в тому, щоб поступово впорядковувати масив, вставляючи нові елементи у вже впорядковану частину. Роботу алгоритму можна описати процедурою Insert_Sort що приймає на вхід невпорядкований масив A:
Insert_Sort(A) 1 forto length[A] 2 do
3
4 while j > 1 і A[j − 1] > x 5 do
6
7
![A[j]\gets\;x](../../../math/5/9/b/59b3882eed41a60bdc70691cc8fc08ae.png)
Процедура впорядковує масив A за неспаданням.
Алгоритм потребує O(1) додаткової пам'яті і O(n2) часу (в середньому і найгіршому випадку, якщо ж масив вже відсортован, то алгоритму потрібно O(n) часу).
Алгоритм ефективний на масивах невеликої довжини (на сучасних комп'ютерах до 100 елементів) за рахунок малої константи при n2. Тому його часто використовують для прискорення роботи інших алгоритмів: якщо необхідно відсортувати невелику частину масиву, то сортують вставками. Також алгоритм є стабільним.
