Сортировка вставками

Идея

Так большинство людей сортирует карты в руке: берём следующую карту и вставляем её на своё место среди уже упорядоченных. Начало A[0..i−1] всегда отсортировано; шаг i вставляет в него A[i], сдвигая бóльшие элементы на одну позицию вправо.

Пример

Сортируем [5, 2, 4, 6, 1, 3] — пример из Кормена. Отсортированное начало выделено жирным.

Шаг	Вставляем	Массив после шага	Сдвигов
1	2	2, 5, 4, 6, 1, 3	1
2	4	2, 4, 5, 6, 1, 3	1
3	6	2, 4, 5, 6, 1, 3	0
4	1	1, 2, 4, 5, 6, 3	4
5	3	1, 2, 3, 4, 5, 6	3

12 сравнений, 9 сдвигов — снова число инверсий.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

INSERTION-SORT(A)
  for i = 1 to n − 1
    key = A[i]
    j = i − 1
    while j ≥ 0 and A[j] > key
      A[j + 1] = A[j]
      j = j − 1
    A[j + 1] = key

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n)	O(n²)	O(n²)	O(1)	да	да

• Время работы O(n + I), где I — число инверсий. У отсортированного массива 0 инверсий (O(n)), у обратного — $\frac{n(n-1)}{2}$ (O(n²)), у случайного — около $\frac{n^2}{4}$.
• Адаптивная: чем ближе массив к отсортированному, тем быстрее она работает.
• Устойчивая: элемент останавливается на первом не большем, поэтому никогда не обгоняет равный.
• Онлайновая: может сортировать данные по мере их поступления.

Когда применять

Маленькие массивы (до нескольких десятков элементов) и почти отсортированные данные. Поэтому быстрые гибридные алгоритмы — TimSort в Array.prototype.sort, introsort в C++ — переключаются на вставки для маленьких кусков.

Использование

import { insertionSort } from 'ts-ds';

const array = [5, 2, 4, 6, 1, 3];
insertionSort(array);

Справочник API

Литература

• Кормен, §2.1 «Сортировка вставкой» и §2.2 «Анализ алгоритмов».
• Кнут, Искусство программирования, т. 3, §5.2.1.