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

TL;DR

Сортировка вставками (insertion sort) поддерживает отсортированный префикс массива и на каждом шаге вставляет в него очередной элемент, сдвигая бо́льшие элементы вправо. Алгоритм прост, работает на месте ([math]\displaystyle{ O(1) }[/math] памяти), устойчив и адаптивен: почти отсортированный массив сортируется за [math]\displaystyle{ O(n) }[/math]. В худшем (обратный массив) и среднем случаях — [math]\displaystyle{ \Theta(n^2) }[/math]. Точная стоимость — [math]\displaystyle{ \Theta(n + \text{inv}) }[/math], где [math]\displaystyle{ \text{inv} }[/math] — число инверсий: каждый сдвиг устраняет ровно одну инверсию. Бинарная версия ищет позицию двоичным поиском ([math]\displaystyle{ O(n\log n) }[/math] сравнений), но сдвиги остаются [math]\displaystyle{ O(n^2) }[/math]. Благодаря простоте и дешевизне на малых отрезках вставки служат базой гибридных сортировок — introsort, mergesort, Timsort (minrun) — переключаются на них при [math]\displaystyle{ n \lt 16\ldots32 }[/math].

Свойство	Значение
Класс	Сортировка сравнением; на месте; устойчивая; онлайн
Лучший случай	[math]\displaystyle{ \Theta(n) }[/math] (уже отсортирован)
Средний случай	[math]\displaystyle{ \Theta(n^2) }[/math] (~[math]\displaystyle{ n^2/4 }[/math] сравнений)
Худший случай	[math]\displaystyle{ \Theta(n^2) }[/math] ([math]\displaystyle{ n(n-1)/2 }[/math] сравнений)
Перемещений	[math]\displaystyle{ \Theta(n + \text{inv}) }[/math] (inv — число инверсий)
Память	[math]\displaystyle{ O(1) }[/math]
Устойчивость	да (строгое «>» при сдвиге)
Адаптивность	высокая ([math]\displaystyle{ O(n) }[/math] на почти отсортированных)
Бинарная версия	[math]\displaystyle{ O(n\log n) }[/math] сравнений, но [math]\displaystyle{ O(n^2) }[/math] перемещений
Роль	база гибридов; малые массивы; Shellsort
Родственники	обзор сортировок, Timsort, Сортировка слиянием

Определения

Сортировка вставками — алгоритм, который поочерёдно (слева направо) вставляет элемент [math]\displaystyle{ a[i] }[/math] в уже отсортированный отрезок [math]\displaystyle{ a[0..i-1] }[/math], сдвигая элементы, большие [math]\displaystyle{ a[i] }[/math], на одну позицию вправо, и кладёт [math]\displaystyle{ a[i] }[/math] на освободившееся место.

Отсортированный префикс — отрезок [math]\displaystyle{ a[0..i-1] }[/math], который поддерживается неубывающим на каждом шаге. Полное отсортирование достигается при [math]\displaystyle{ i = n }[/math].

Устойчивость (stability) — равные элементы сохраняют исходный порядок. Вставки устойчивы, потому что сдвигаются только элементы, строго большие вставляемого.

На месте (in-place) — используется [math]\displaystyle{ O(1) }[/math] дополнительной памяти (одна переменная под вставляемый элемент).

Онлайн-алгоритм — может сортировать данные по мере их поступления, имея отсортированными уже прочитанные элементы.

Инверсия — пара индексов [math]\displaystyle{ i \lt j }[/math] с [math]\displaystyle{ a[i] \gt a[j] }[/math]; мера «беспорядка». В сортировке вставками каждый сдвиг устраняет ровно одну инверсию.

Бинарная сортировка вставками — вариант, в котором позиция вставки ищется двоичным поиском за [math]\displaystyle{ O(\log i) }[/math], но перемещение элементов всё равно выполняется сдвигом.

Shellsort — обобщение: сортировка вставками по подпоследовательностям с убывающими шагами; элементы перемещаются на большие расстояния, что ускоряет последующие проходы.

Обозначения. [math]\displaystyle{ n }[/math] — длина массива; [math]\displaystyle{ i }[/math] — текущий индекс; [math]\displaystyle{ \text{inv} }[/math] — число инверсий; [math]\displaystyle{ \log }[/math] — двоичный.

Мотивация и интуиция

Сортировка вставками — вероятно, простейший алгоритм сортировки, и у него есть три свойства, делающие его незаменимым на практике: на месте, устойчив и адаптивен. На массиве, где беспорядка мало (почти отсортированном, или «немного подправленном»), она обгоняет и quicksort, и mergesort, потому что делает работу, пропорциональную числу инверсий.

Идея в одном абзаце: держим префикс отсортированным. Вставляя [math]\displaystyle{ a[i] }[/math], достаточно раздвинуть часть префикса, чтобы найти место; чем меньше инверсий у [math]\displaystyle{ a[i] }[/math], тем меньше сдвигов. В пределе (массив уже отсортирован) каждый элемент вставляется на своё место за одно сравнение — суммарно [math]\displaystyle{ n-1 }[/math], то есть [math]\displaystyle{ O(n) }[/math].

Именно поэтому вставки используют как «хвост» рекурсивных сортировок: на коротких отрезках рекурсия и накладные расходы дороже, чем прямая вставка; а почти отсортированные данные — частая реальность.

Рис. 1. Вставляем элемент в отсортированный префикс, сдвигая большие элементы вправо.

Рис. 2. Сдвигов ровно столько, сколько инверсий: отсортированное — [math]\displaystyle{ O(n) }[/math], обратное — [math]\displaystyle{ \Theta(n^2) }[/math].

Устройство

Два «указателя»: граница отсортированного префикса [math]\displaystyle{ i }[/math] и позиция [math]\displaystyle{ j }[/math] внутри префикса, идущая справа налево в поиске места. Вставляемый элемент сохраняется в переменной (это и есть дополнительная «память» [math]\displaystyle{ O(1) }[/math]), затем сдвигаются элементы.

• Массив. Сдвиг — это запись элементов на соседние позиции ([math]\displaystyle{ O(n) }[/math] в худшем); вставка дешёва по количеству обменов, но перемещения памяти могут быть дорогими.
• Связный список. Сдвиг заменяется обновлением указателей; но поиск места остаётся линейным, поэтому общая сложность всё равно [math]\displaystyle{ O(n^2) }[/math] (см. рис. 5).

Рис. 3. Массив после каждого шага: префикс слева растёт и остаётся отсортированным.

Операции и алгоритмы

Операция: Insertion-Sort (линейный поиск места)

Идея. Для каждого [math]\displaystyle{ i }[/math] «протаскиваем» [math]\displaystyle{ a[i] }[/math] влево, пока предыдущий элемент больше.

Пошаговое описание:

1. Для [math]\displaystyle{ i }[/math] от [math]\displaystyle{ 1 }[/math] до [math]\displaystyle{ n-1 }[/math]: сохранить v ← a[i], j ← i-1.
2. Пока j ≥ 0 и a[j] > v: сдвинуть a[j] вправо (a[j+1] ← a[j]), j ← j-1.
3. Положить a[j+1] ← v.

Инвариант. Перед обработкой [math]\displaystyle{ a[i] }[/math] отрезок [math]\displaystyle{ a[0..i-1] }[/math] отсортирован; элементы [math]\displaystyle{ a[i..n-1] }[/math] ещё не тронуты.

Алгоритм Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: перед шагом i отрезок a[0..i−1] отсортирован
Сложность: O(n + inv) перемещений; сравнений от n−1 (лучший) до n(n−1)/2 (худший)

1  for i ← 1 to n − 1
2      v ← a[i]
3      j ← i − 1
4      while j ≥ 0 and a[j] > v          # строгое > → устойчивость
5          a[j + 1] ← a[j]
6          j ← j − 1
7      a[j + 1] ← v

Разбор. [5,2,4,6,1,3] (см. рис. 3): после шагов получаем [2,4,5,6|1,3] → [1,2,4,5,6|3] → [1,2,3,4,5,6]; всего 9 сдвигов = число инверсий.

Сложность. Лучший [math]\displaystyle{ \Theta(n) }[/math], средний [math]\displaystyle{ \Theta(n^2) }[/math], худший [math]\displaystyle{ \Theta(n^2) }[/math]; память [math]\displaystyle{ O(1) }[/math].

Крайние случаи. Отсортированный массив — [math]\displaystyle{ n-1 }[/math] сравнение и 0 сдвигов. Обратный — [math]\displaystyle{ n(n-1)/2 }[/math] сравнений и сдвигов. [math]\displaystyle{ n \le 1 }[/math] — ничего.

Операция: Binary-Insertion-Sort

Идея. Позицию вставки искать двоичным поиском в отсортированном префиксе (см. рис. 4).

Алгоритм Binary-Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован
Сложность: O(n log n) сравнений, но O(n²) перемещений ⇒ O(n²) времени

1  for i ← 1 to n − 1
2      v ← a[i]
3      lo ← 0 ; hi ← i                    # верхняя граница: первый p, где v < a[p]
4      while lo < hi
5          mid ← lo + ⌊(hi − lo) / 2⌋
6          if v < a[mid]: hi ← mid else lo ← mid + 1
7      for j ← i downto lo + 1
8          a[j] ← a[j − 1]               # сдвиг
9      a[lo] ← v

Разбор. На рис. 4 для v = 4 позиция находится за 2–3 сравнения вместо 3–4.

Сложность. Сравнений [math]\displaystyle{ O(n\log n) }[/math]; перемещений по-прежнему [math]\displaystyle{ O(n^2) }[/math] → суммарно [math]\displaystyle{ O(n^2) }[/math].

Крайние случаи. Двоичный поиск ищет верхнюю границу — равные не переставляются, код устойчив.

Рис. 4. Меньше сравнений, но сдвиги те же: [math]\displaystyle{ O(n^2) }[/math] по перемещениям сохраняется.

Операция: сортировка вставками на списке

Идея. Идём по списку; каждый очередной узел вставляем в отсортированную часть, меняя указатели.

Алгоритм List-Insertion-Sort(head)
Вход:  односвязный список
Выход: отсортированный список
Сложность: O(n²) сравнений; перемещений — O(1) на вставку

1  sorted ← NIL
2  for each узел cur в исходном порядке
3      next ← cur.next
4      вставить cur в sorted на нужное место (линейный поиск)

Крайние случаи. Вставка в начало; дубликаты (вставляем после равных — устойчиво).

Рис. 5. На списке вставка — обновление указателей, но поиск места линейный.

Сводная таблица сложности

Операция	Лучший	Средний	Худший	Память
Сравнения	[math]\displaystyle{ n-1 }[/math]	[math]\displaystyle{ \approx n^2/4 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	—
Перемещения (сдвиги)	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \approx n^2/4 }[/math]	[math]\displaystyle{ n(n-1)/2 }[/math]	—
Всего	[math]\displaystyle{ \Theta(n) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
Binary-Insertion: сравнения	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(1) }[/math]
Binary-Insertion: перемещения	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ \Theta(n^2) }[/math]	[math]\displaystyle{ O(1) }[/math]
Точная формула	—	—	[math]\displaystyle{ \Theta(n + \text{inv}) }[/math]	—

Оговорка: точная оценка [math]\displaystyle{ \Theta(n+\text{inv}) }[/math] показывает адаптивность: при малом числе инверсий вставки линейны и обгоняют «быстрые» сортировки. На списке обменов [math]\displaystyle{ O(1) }[/math], но сравнений [math]\displaystyle{ O(n^2) }[/math].

Трассировка примера

a = [5, 2, 4, 6, 1, 3] (см. рис. 3).

[math]\displaystyle{ i }[/math]	Вставляем	Действие	Массив	Сдвиги
1	2	2 перед 5	[2, 5, 4, 6, 1, 3]	1
2	4	между 2 и 5	[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	между 2 и 4	[1, 2, 3, 4, 5, 6]	3

Всего сдвигов: [math]\displaystyle{ 1+1+0+4+3 = 9 }[/math] — ровно число инверсий массива [5,2,4,6,1,3]. Трассировка сверена с реализацией из раздела «Служебное».

Корректность и оценка сложности

Корректность (инвариант)

Инвариант цикла. Перед обработкой [math]\displaystyle{ a[i] }[/math] массив [math]\displaystyle{ a[0..i-1] }[/math] отсортирован; элементы [math]\displaystyle{ a[i..n-1] }[/math] не тронуты.

База. [math]\displaystyle{ i = 1 }[/math]: префикс из одного элемента [math]\displaystyle{ a[0] }[/math] отсортирован.

Сохранение. При вставке [math]\displaystyle{ v = a[i] }[/math] мы находим первую справа позицию, где a[j] ≤ v, сдвигая строго большие элементы вправо. После этого [math]\displaystyle{ a[j+1] = v }[/math], и префикс [math]\displaystyle{ a[0..i] }[/math] неубывающий: элементы слева [math]\displaystyle{ \le v }[/math] (по построению), справа были [math]\displaystyle{ \gt v }[/math] и сдвинуты. Инвариант сохранён.

Завершение. При [math]\displaystyle{ i = n-1 }[/math] (после вставки) весь массив отсортирован. [math]\displaystyle{ \square }[/math]

Устойчивость

Сдвигаются только элементы со строгим a[j] > v; равные остаются слева от [math]\displaystyle{ v }[/math] и не меняют взаимного порядка. Значит, алгоритм устойчив.

Точная стоимость

Каждый сдвиг переносит больший элемент через меньший, устраняя ровно одну инверсию; обратные операции инверсий не создают. Значит, число сдвигов равно [math]\displaystyle{ \text{inv}(a) }[/math] — числу инверсий исходного массива. К этому добавляется по одной записи [math]\displaystyle{ v }[/math] на элемент, то есть

[math]\displaystyle{ \text{перемещений} = \text{inv}(a) + (n - 1), \qquad \text{сравнений} \le \text{inv}(a) + (n-1). }[/math]

Отсюда: уже отсортированный массив — [math]\displaystyle{ O(n) }[/math], обратный — [math]\displaystyle{ \Theta(n^2) }[/math].

Бинарная версия

Позиция ищется за [math]\displaystyle{ \lceil\log_2 i\rceil }[/math] сравнений, суммарно [math]\displaystyle{ O(n\log n) }[/math]. Но сдвиг остаётся [math]\displaystyle{ \Theta(i) }[/math] в худшем, поэтому по времени алгоритм всё ещё [math]\displaystyle{ O(n^2) }[/math]; выигрыш — только в числе сравнений (важен при дорогом сравнении ключей).

Сравнение с альтернативами

Алгоритм	Средний	Лучший	Устойчив	Память	Ниша
Вставками	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(1) }[/math]	малые, почти отсортированные
Выбором	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n^2) }[/math]	нет	[math]\displaystyle{ O(1) }[/math]	мало обменов; вставки обычно лучше
Пузырьком	[math]\displaystyle{ O(n^2) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(1) }[/math]	учебный; вставки эффективнее
Слиянием	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	да	[math]\displaystyle{ O(n) }[/math]	большие [math]\displaystyle{ n }[/math], списки
Быстрая	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n\log n) }[/math]	нет	[math]\displaystyle{ O(\log n) }[/math]	большие [math]\displaystyle{ n }[/math], средняя скорость
Timsort	[math]\displaystyle{ O(n\log n) }[/math]	[math]\displaystyle{ O(n) }[/math]	да	[math]\displaystyle{ O(n) }[/math]	реальные данные

Рис. 6. Вставки проигрывают по асимптотике, но выигрывают на малых и почти отсортированных данных; отсюда — роль базы гибридов.

Вердикт. Для больших случайных массивов вставки не годятся ([math]\displaystyle{ O(n^2) }[/math]). Их ниша — короткие отрезки (внутри гибридов) и почти отсортированные данные. Именно поэтому introsort, mergesort и Timsort используют вставки как «хвост» рекурсии.

Где применяется

1. База гибридных сортировок. introsort (std::sort), mergesort, Timsort переключаются на вставки на коротких отрезках (порог 16–32). Почему: рекурсия и накладные расходы на малых отрезках дороже прямой вставки [1][4][6].

1. Timsort и minrun. Timsort удлиняет короткие серии до minrun бинарными вставками — прямое использование варианта из этой статьи [5].

1. Почти отсортированные данные. Обновлённые таблицы, инкрементальные вычисления, «подправленные» списки: стоимость [math]\displaystyle{ \Theta(n+\text{inv}) }[/math] делает вставки самыми быстрыми [1][3].

1. Онлайн-вставка. Поддержание отсортированного порядка при потоке элементов; на связном списке вставка = обновление указателей [3].

1. Shellsort. Вставки на подпоследовательностях с убывающими шагами — практичный [math]\displaystyle{ O(n^{1.3}) }[/math]–[math]\displaystyle{ O(n^{1.5}) }[/math] алгоритм на средних массивах [2][3].

Рис. 7. Вставки как база гибридов и для малых/почти отсортированных данных.

Историческая справка

Сортировка вставками — одна из древнейших известных сортировок; её описывал ещё Джон Мокли (John Mauchly) в 1946 году, а систематический анализ дал Дональд Кнут в The Art of Computer Programming, т. 3 (раздел 5.2.1): там же разобраны бинарный вариант, среднее число сравнений [math]\displaystyle{ \approx n^2/4 }[/math] и связь с инверсиями [2]. Простота и адаптивность обеспечили ей место в учебниках как первого алгоритма сортировки (CLRS, гл. 2) [1].

Дональд Шелл в 1959 году обобщил вставки на подпоследовательности с убывающим шагом — Shellsort, заметно ускорив алгоритм при малых накладных расходах [2][7]. Бинарный вариант (поиск позиции делением пополам) известен как binary insertion sort. В современных библиотеках вставки живут как «хвост» introsort/Timsort, где работают на коротких отрезках [4][5][6].

Типичные ошибки и подводные камни

• Non-strict сравнение. a[j] >= v при сдвиге нарушает устойчивость; нужно строгое >.
• Ошибка границ. j ≥ 0 обязательно, иначе выход за массив при вставке в начало.
• Не сохранить v. Если не держать вставляемый элемент в переменной, его перезапишет сдвиг.
• Ожидание [math]\displaystyle{ O(n\log n) }[/math] от бинарной версии. Сравнений меньше, но перемещения остаются [math]\displaystyle{ O(n^2) }[/math].
• Применение к большим случайным массивам. [math]\displaystyle{ O(n^2) }[/math] катастрофичен; для больших [math]\displaystyle{ n }[/math] — гибриды.
• Дорогие перемещения. Сдвиг больших структур (не чисел) медленный — либо список, либо обмен.
• Список вместо массива без нужды. На списке вставка дешевле по указателям, но кэш хуже; часто массив быстрее на практике.
• Забыть про адаптивность. На почти отсортированных данных вставки могут обогнать quicksort — не сбрасывайте их со счетов в гибридах.
• Путаница с сортировкой выбором. Выбором не адаптивна и неустойчива; вставки обычно выигрывают.
• Худший вход. Обратный массив — [math]\displaystyle{ \Theta(n^2) }[/math]; в гибридах от него спасает порог и переход на другой алгоритм.

Задачи для практики

1. Базовая реализация. Реализуйте сортировку вставками и посчитайте сравнения/сдвиги. Подсказка: инвариант — отсортированный префикс.

1. Инверсии. Докажите, что число сдвигов равно числу инверсий; проверьте на примере. Подсказка: каждый сдвиг устраняет ровно одну инверсию.

1. Лучший/худший. Для [math]\displaystyle{ n = 1000 }[/math] найдите точные числа сравнений на отсортированном и обратном массивах. Подсказка: [math]\displaystyle{ n-1 }[/math] и [math]\displaystyle{ n(n-1)/2 }[/math].

1. Бинарная версия. Реализуйте binary insertion sort; сравните число сравнений с обычной. Подсказка: верхняя граница для устойчивости.

1. Список. Отсортируйте односвязный список вставками; оцените сравнения и обновления указателей. Подсказка: вставка между узлами.

1. Порог гибрида. Quicksort + вставки при [math]\displaystyle{ n \lt k }[/math]: подберите [math]\displaystyle{ k }[/math] по бенчмарку. Подсказка: 16–32.

1. Почти отсортировано. Дан массив, где [math]\displaystyle{ k }[/math] элементов не на месте; оцените время вставок через инверсии. Подсказка: [math]\displaystyle{ \Theta(n + \text{inv}) }[/math].

1. Shellsort. Реализуйте Shellsort с шагами Хиббарда и сравните с обычными вставками. Подсказка: вставки по подпоследовательностям.

Связанные темы

• Сортировки — обзор алгоритмов и нижняя граница [math]\displaystyle{ \Omega(n\log n) }[/math].
• Сортировка Шелла — обобщение вставок на убывающие шаги.
• Сортировка пузырьком — обменный родственник; вставки почти всегда его быстрее.
• Быстрая сортировка — introsort и переключение на вставки.
• Сортировка слиянием — гибрид с вставками на малых отрезках.
• Timsort — бинарные вставки для удлинения runs (minrun).
• Пирамидальная сортировка — другой [math]\displaystyle{ O(1) }[/math]-по-памяти алгоритм.
• Асимптотическая сложность — лучший/средний/худший случаи.

Источники

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C. Introduction to Algorithms (CLRS). 3rd ed. — MIT Press, 2009. — Гл. 2.1 «Insertion sort» (инвариант, анализ).
2. Knuth D. E. The Art of Computer Programming. Vol. 3: Sorting and Searching. — Addison-Wesley, 2nd ed., 1998. — §5.2.1 (insertion sort), §5.2.1 (Shellsort).
3. Sedgewick R., Wayne K. Algorithms. 4th ed. — Addison-Wesley, 2011. — §2.1 (Elementary Sorts).
4. Musser D. R. Introspective Sorting and Selection Algorithms // Software: Practice and Experience. — 1997 (переключение на вставки в introsort).
5. Peters T. listsort.txt (Timsort, бинарные вставки) URL: https://github.com/python/cpython/blob/main/Objects/listsort.txt .
6. Wikipedia: Insertion sort. URL: https://en.wikipedia.org/wiki/Insertion_sort .
7. Shell D. L. A High-Speed Sorting Procedure // CACM. — 1959. — Vol. 2, № 7 .