Просмотр кода страницы Сортировка вставками

== TL;DR ==

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

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

== Определения ==

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

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

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

'''На месте (in-place)''' — используется <math>O(1)</math> дополнительной памяти (одна переменная под вставляемый элемент).

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

'''Инверсия''' — пара индексов <math>i < j</math> с <math>a[i] > a[j]</math>; мера «беспорядка». В сортировке вставками каждый сдвиг устраняет ровно одну инверсию.

'''Сдвиг''' — запись <math>a[j+1] \leftarrow a[j]</math>, переносящая элемент на одну позицию вправо. Каждый сдвиг устраняет ровно одну инверсию, поэтому сдвигов ровно <math>\text{inv}(a)</math>.

'''Перемещение (запись)''' — любая запись элемента в массив: сдвиг или запись вставляемого <math>v</math> на освободившееся место. Линейная версия делает <math>\text{inv}(a) + (n-1)</math> перемещений; у отсортированного массива это <math>n-1</math>, а не 0.

'''Бинарная сортировка вставками''' — вариант, в котором позиция вставки ищется '''двоичным поиском'''; в худшем случае на префиксе длины <math>i</math> требуется <math>\lceil\log_2(i+1)\rceil</math> сравнений (<math>O(\log i)</math> асимптотически), но перемещение элементов всё равно выполняется сдвигом.

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

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

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

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

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

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

[[Файл:iv-01-idea.svg|thumb|700px|Рис. 1. Вставка 4 в отсортированный префикс <math>[2,5,7,9]</math>: 5, 7, 9 сдвигаются вправо, 4 встаёт между 2 и 5; префикс снова отсортирован.]]

[[Файл:iv-02-inversions.svg|thumb|700px|Рис. 2. Сдвигов ровно столько, сколько инверсий: у отсортированного массива 0 сдвигов, но <math>n-1</math> записей; у обратного — <math>n(n-1)/2</math> сдвигов. Полная стоимость — <math>\Theta(n+\text{inv})</math>.]]

== Устройство ==

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

* '''Массив.''' Сдвиг — это запись элементов на соседние позиции (<math>O(n)</math> в худшем); обменов нет, но перемещения памяти могут быть дорогими.
* '''Связный список.''' Сдвиг заменяется обновлением указателей; но поиск места остаётся линейным, поэтому общая сложность всё равно <math>O(n^2)</math> (см. рис. 5).

[[Файл:iv-03-trace.svg|thumb|700px|Рис. 3. Состояние массива после каждого шага: зелёный префикс отсортирован, синий элемент — вставленный на этом шаге; справа — число сдвигов.]]

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

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

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

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

# Для <math>i</math> от <math>1</math> до <math>n-1</math>: сохранить <code>v ← a[i]</code>, <code>j ← i-1</code>.
# Пока <code>j ≥ 0</code> и <code>a[j] &gt; v</code>: сдвинуть <code>a[j]</code> вправо (<code>a[j+1] ← a[j]</code>), <code>j ← j-1</code>.
# Положить <code>a[j+1] ← v</code>.

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

<syntaxhighlight lang="text">
Алгоритм Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован по неубыванию
Инвариант: перед шагом i отрезок a[0..i−1] отсортирован
Сложность: сдвигов ровно inv; перемещений inv + (n−1); сравнений от 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
</syntaxhighlight>

'''Разбор.''' <code>[5,2,4,6,1,3]</code> (см. рис. 3): после шагов получаем <code>[2,4,5,6|1,3]</code> → <code>[1,2,4,5,6|3]</code> → <code>[1,2,3,4,5,6]</code>; всего 9 сдвигов = число инверсий, 5 записей <math>v</math> и <math>9+5=14</math> перемещений; сравнений — 12 (см. трассировку ниже).

'''Сложность.''' Лучший <math>\Theta(n)</math> — это <math>n-1</math> сравнений, 0 сдвигов и <math>n-1</math> перемещений; средний и худший <math>\Theta(n^2)</math>; память <math>O(1)</math>.

'''Крайние случаи.''' Отсортированный массив — <math>n-1</math> сравнений, 0 сдвигов и <math>n-1</math> перемещений. Обратный — <math>n(n-1)/2</math> сравнений и сдвигов плюс <math>n-1</math> записей, итого <math>n(n-1)/2 + n-1</math> перемещений. <math>n \le 1</math> — ничего.

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

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

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

# Сохранить <math>v \leftarrow a[i]</math>, <code>lo ← 0</code>, <code>hi ← i</code>.
# Двоичным поиском найти '''верхнюю границу''' — первый индекс <math>p</math>, где <math>v < a[p]</math>: пока <code>lo &lt; hi</code>, взять <code>mid ← lo + ⌊(hi − lo)/2⌋</code>; если <code>v &lt; a[mid]</code>, то <code>hi ← mid</code>, иначе <code>lo ← mid + 1</code>.
# Сдвинуть <code>a[lo..i−1]</code> на одну позицию вправо.
# Положить <code>a[lo] ← v</code>.

'''Инвариант.''' В префиксе <math>a[0..i-1]</math> все элементы левее <code>lo</code> не больше <math>v</math>, все начиная с <code>hi</code> строго больше <math>v</math>; позиция вставки лежит в <code>[lo, hi]</code>. После цикла <code>lo = hi</code> — первая позиция, где <math>a[p] > v</math> (верхняя граница).

<syntaxhighlight lang="text">
Алгоритм Binary-Insertion-Sort(a)
Вход:  массив a[0..n−1]
Выход: a отсортирован
Инвариант: позиция вставки v лежит в [lo, hi]; a[0..lo−1] ≤ v < a[hi..i−1]
Сложность: 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
</syntaxhighlight>

'''Разбор.''' Вставляем <math>v = 2</math> в <math>[1,3,4,5,6,7,8,9]</math> (см. рис. 4):

# <code>lo=0, hi=8, mid=4</code>, <code>a[4]=6</code>, <math>2<6</math> → <code>hi=4</code>;
# <code>lo=0, hi=4, mid=2</code>, <code>a[2]=4</code>, <math>2<4</math> → <code>hi=2</code>;
# <code>lo=0, hi=2, mid=1</code>, <code>a[1]=3</code>, <math>2<3</math> → <code>hi=1</code>;
# <code>lo=0, hi=1, mid=0</code>, <code>a[0]=1</code>, <math>2\ge 1</math> → <code>lo=1</code>.

Итог: <code>lo = hi = 1</code>, 4 сравнения, 7 сдвигов, 8 перемещений; линейный поиск справа делает 8 сравнений. Позиция вставки — 1.

'''Сложность.''' В худшем случае <math>\lceil\log_2(i+1)\rceil</math> сравнений на вставку, суммарно <math>O(n\log n)</math>; сдвигов <math>\text{inv}</math>, перемещений <math>\text{inv} + (n-1)</math>, в худшем <math>\Theta(n^2)</math>. На отсортированном массиве сравнений всё равно <math>\Theta(n\log n)</math>, а линейная версия делает <math>n-1</math> — бинарная теряет адаптивность по сравнениям.

'''Крайние случаи.''' <code>lo = i</code> — сдвигов нет, одна запись; <code>lo = 0</code> — <math>i</math> сдвигов; дубликаты — верхняя граница сохраняет устойчивость; <math>n \le 1</math> — ничего.

[[Файл:iv-04-binary.svg|thumb|700px|Рис. 4. Бинарный поиск позиции для <math>v = 2</math> в <math>[1,3,4,5,6,7,8,9]</math>: четыре сравнения (<math>\text{mid} = 4, 2, 1, 0</math>) вместо восьми при линейном поиске; сдвиги при этом остаются <math>O(n^2)</math>.]]

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

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

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

# Обходить исходный список, сохраняя <code>next ← cur.next</code>.
# Найти в <code>sorted</code> первый узел <code>p</code> с ключом <code>&gt; cur.key</code>, запоминая <code>prev</code>.
# Вставить <code>cur</code> между <code>prev</code> и <code>p</code>.
# Перейти к <code>next</code>.

'''Инвариант.''' <code>sorted</code> отсортирован и содержит все обработанные узлы; необработанная часть не изменена.

<syntaxhighlight lang="text">
Алгоритм List-Insertion-Sort(head)
Вход:  односвязный список
Выход: отсортированный список
Инвариант: sorted отсортирован и содержит все обработанные узлы
Сложность: O(n²) сравнений; обновлений указателей — O(1) на вставку

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

'''Разбор.''' <code>[5,2,4,6,1,3]</code> → <code>[5]</code> → <code>[2,5]</code> → <code>[2,4,5]</code> → <code>[2,4,5,6]</code> → <code>[1,2,4,5,6]</code> → <code>[1,2,3,4,5,6]</code>; всего 10 сравнений; на каждую вставку — <math>O(1)</math> обновлений указателей.

'''Сложность.''' <math>O(n^2)</math> сравнений; <math>O(1)</math> обновлений указателей на вставку; <math>O(1)</math> дополнительной памяти (указатели).

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

[[Файл:iv-05-linkedlist.svg|thumb|700px|Рис. 5. Вставка узла 4 в отсортированную часть <math>[2,5,8]</math>: обновляются указатели, но поиск места остаётся линейным.]]

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

{| class="wikitable"
|-
! Операция !! Лучший !! Средний !! Худший !! Память
|-
| Линейная: сравнения || <math>n-1</math> || <math>\approx n^2/4</math> || <math>n(n-1)/2</math> || —
|-
| Линейная: сдвиги || <math>0</math> || <math>\approx n^2/4</math> || <math>n(n-1)/2</math> || —
|-
| Линейная: записи <math>v</math> || <math>n-1</math> || <math>n-1</math> || <math>n-1</math> || —
|-
| Линейная: перемещения || <math>n-1</math> || <math>\approx n^2/4 + n-1</math> || <math>n(n-1)/2 + n-1</math> || —
|-
| Линейная: всего || <math>\Theta(n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>O(1)</math>
|-
| Бинарная: сравнения || <math>\Theta(n\log n)</math> || <math>\Theta(n\log n)</math> || <math>\Theta(n\log n)</math> || —
|-
| Бинарная: сдвиги || <math>0</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || —
|-
| Бинарная: перемещения || <math>n-1</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>O(1)</math>
|-
| Бинарная: всего || <math>\Theta(n\log n)</math> || <math>\Theta(n^2)</math> || <math>\Theta(n^2)</math> || <math>O(1)</math>
|}

Точная стоимость линейной версии: перемещения = <math>\text{inv}(a) + (n-1)</math>, сравнения <math>\le \text{inv}(a) + (n-1)</math>. Для бинарной версии сравнения <math>\Theta(n\log n)</math> даже на отсортированном массиве; выигрыш — только при дорогих сравнениях.

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

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

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

{| class="wikitable"
|-
! <math>i</math> !! Вставляем !! Действие !! Массив !! Сравнения !! Сдвиги !! Перемещения
|-
| 1 || 2 || 2 перед 5 || <code>[2, 5, 4, 6, 1, 3]</code> || 1 || 1 || 2
|-
| 2 || 4 || между 2 и 5 || <code>[2, 4, 5, 6, 1, 3]</code> || 2 || 1 || 2
|-
| 3 || 6 || на месте || <code>[2, 4, 5, 6, 1, 3]</code> || 1 || 0 || 1
|-
| 4 || 1 || в начало || <code>[1, 2, 4, 5, 6, 3]</code> || 4 || 4 || 5
|-
| 5 || 3 || между 2 и 4 || <code>[1, 2, 3, 4, 5, 6]</code> || 4 || 3 || 4
|-
| '''Всего''' || || || || '''12''' || '''9''' || '''14'''
|}

9 сдвигов = 9 инверсий; 5 записей <math>v</math>; <math>14 = 9 + 5 = \text{inv} + (n-1)</math> перемещений; 12 сравнений <math>\le 14</math>.

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

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

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

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

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

'''Завершение.''' При <math>i = n-1</math> (после вставки) весь массив отсортирован. <math>\square</math>

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

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

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

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

<math display="block">\text{перемещений} = \text{inv}(a) + (n - 1), \qquad \text{сравнений} \le \text{inv}(a) + (n-1).</math>

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

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

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

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

{| class="wikitable"
|-
! Алгоритм !! Средний !! Лучший !! Устойчив !! Память !! Ниша
|-
| '''Вставками''' || <math>O(n^2)</math> || <math>O(n)</math> || да || <math>O(1)</math> || малые, почти отсортированные
|-
| Выбором || <math>O(n^2)</math> || <math>O(n^2)</math> || нет || <math>O(1)</math> || мало обменов; вставки обычно лучше
|-
| Пузырьком || <math>O(n^2)</math> || <math>O(n)</math> || да || <math>O(1)</math> || учебный; вставки эффективнее
|-
| Слиянием || <math>O(n\log n)</math> || <math>O(n\log n)</math> || да || <math>O(n)</math> || большие <math>n</math>, списки
|-
| Быстрая || <math>O(n\log n)</math> || <math>O(n\log n)</math> || нет || <math>O(\log n)</math> || большие <math>n</math>, средняя скорость
|-
| Timsort || <math>O(n\log n)</math> || <math>O(n)</math> || да || <math>O(n)</math> || реальные данные
|}

[[Файл:iv-06-compare.svg|thumb|700px|Рис. 6. Шесть сортировок рядом: вставки уступают по средней асимптотике, но устойчивы, адаптивны (лучший случай <math>O(n)</math>) и не требуют дополнительной памяти; Timsort устойчив и в лучшем случае <math>O(n)</math>.]]

'''Вердикт.''' Для больших случайных массивов вставки не годятся (<math>O(n^2)</math>). Их ниша — '''короткие отрезки''' (внутри гибридов) и '''почти отсортированные''' данные (см. рис. 6). Timsort устойчив и в лучшем случае <math>O(n)</math>; quicksort неустойчив и в лучшем случае <math>O(n\log n)</math>. Именно поэтому introsort, mergesort и Timsort используют вставки как «хвост» рекурсии.

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

# '''База гибридных сортировок.''' introsort (<code>std::sort</code>) и mergesort переключаются на вставки на коротких отрезках; типичный порог отсечения — 16–32 элемента. Почему: рекурсия и накладные расходы на малых отрезках дороже прямой вставки [1][4][6].

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

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

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

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

Все перечисленные ниши схематично показаны на рис. 7.

[[Файл:iv-07-applications.svg|thumb|700px|Рис. 7. Вставки как база гибридов: порог отсечения introsort/mergesort — 16–32, minrun Timsort — 32–64; почти отсортированные данные и онлайн-вставка.]]

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

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

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

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

* '''Нестрогое сравнение (non-strict).''' <code>a[j] &gt;= v</code> при сдвиге нарушает устойчивость; нужно строгое <code>&gt;</code>.
* '''Ошибка границ.''' <code>j ≥ 0</code> обязательно, иначе выход за массив при вставке в начало.
* '''Не сохранить <code>v</code>.''' Если не держать вставляемый элемент в переменной, его перезапишет сдвиг.
* '''Ожидание <math>O(n\log n)</math> от бинарной версии.''' Сравнений меньше в худшем и среднем, но на отсортированном массиве линейная делает <math>n-1</math>, а бинарная — <math>\Theta(n\log n)</math>; перемещения в обеих версиях остаются <math>O(n^2)</math>.
* '''Применение к большим случайным массивам.''' <math>O(n^2)</math> катастрофичен; для больших <math>n</math> — гибриды.
* '''Дорогие перемещения.''' Сдвиг больших структур медленный — сортировка указателей/индексов (индирекция), связный список или <code>memmove</code>; обмен сам по себе тоже перемещает записи.
* '''Список вместо массива без нужды.''' На списке вставка дешевле по указателям, но кэш хуже; часто массив быстрее на практике.
* '''Забыть про адаптивность.''' На почти отсортированных данных вставки могут обогнать quicksort — не сбрасывайте их со счетов в гибридах.
* '''Путаница с сортировкой выбором.''' Выбором не адаптивна и неустойчива; вставки обычно выигрывают.
* '''Худший вход.''' Обратный массив — <math>\Theta(n^2)</math>; в гибридах спасает не порог, а fallback: introsort переходит на heapsort при глубокой рекурсии, mergesort/Timsort — на слияние.
* '''Переполнение <code>mid</code>.''' <code>(lo + hi) / 2</code> может переполниться на больших индексах; используйте <code>lo + (hi − lo) / 2</code>.
* '''Нижняя граница вместо верхней.''' Если искать первый элемент <code>≥ v</code>, равные окажутся справа и устойчивость нарушится; нужна верхняя граница (<code>v &lt; a[mid]</code>).

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

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

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

# '''Лучший/худший.''' Для <math>n = 1000</math> найдите точные числа сравнений на отсортированном и обратном массивах. ''Подсказка:'' <math>n-1</math> и <math>n(n-1)/2</math>.

# '''Бинарная версия.''' Реализуйте binary insertion sort; сравните число сравнений с обычной на случайном, отсортированном и обратном массивах; объясните, почему на отсортированном бинарная проигрывает по сравнениям. ''Подсказка:'' верхняя граница для устойчивости; <math>\lceil\log_2(i+1)\rceil</math>.

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

# '''Порог гибрида.''' Quicksort + вставки при <math>n < k</math>: подберите <math>k</math> по бенчмарку. ''Подсказка:'' 16–32 для порога отсечения; minrun Timsort 32–64 — другое.

# '''Почти отсортировано.''' Дан массив с <math>\text{inv}</math> инверсиями; оцените время вставок как <math>\Theta(n + \text{inv})</math>. ''Подсказка:'' сдвигов ровно <math>\text{inv}</math>, записей <math>v</math> — <math>n-1</math>.

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

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

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

== Источники ==

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

[[Category:Сортировки]]