Сортировка вставками¶
Сортировка вставками — алгоритм сортировки, при котором элементы входной последовательности поочерёдно извлекаются и вставляются в уже упорядоченную часть массива на подходящую позицию. Относится к классу простых (базовых) алгоритмов сортировки, работающих «на месте», то есть без выделения дополнительной памяти, пропорциональной размеру массива. Характеризуется квадратичной сложностью в худшем и среднем случаях и линейной — на почти отсортированных данных.
¶Идея алгоритма
Алгоритм напоминает способ, которым человек раскладывает карты в руке: очередная карта берётся из неразобранной части и вставляется в нужное место среди уже упорядоченных. Формально массив делится на две части: отсортированный префикс (в начале) и неотсортированный остаток. На каждом шаге первый элемент остатка помещается в префикс так, чтобы порядок в нём сохранился. Процесс повторяется, пока остаток не опустеет.
Ключевая операция — сдвиг: чтобы освободить место для вставляемого элемента, все элементы префикса, большие него, сдвигаются на одну позицию вправо. Это позволяет обойтись без обмена значений и без дополнительного массива.
¶Пошаговое описание
Для массива из n элементов:
- Считать первый элемент (индекс 0) отсортированным префиксом.
- Взять элемент с индексом i (i от 1 до n−1) — это «ключ».
- Сравнивать ключ с элементами префикса справа налево, сдвигая каждый больший элемент на позицию вправо.
- Как только найден элемент, не превосходящий ключ, или достигнут левый край, вставить ключ на освободившееся место.
- Повторять шаги 2–4 до конца массива.
После завершения всех проходов массив отсортирован по возрастанию (при соответствующем выборе направления сравнения — по убыванию).
¶Пример
Сортировка последовательности [5, 2, 4, 6, 1, 3]:
| Шаг | Состояние массива | Пояснение | |
|---|---|---|---|
| 0 | 5 \ | 2 4 6 1 3 | префикс из одного элемента |
| 1 | 2 5 \ | 4 6 1 3 | 2 вставлена перед 5 |
| 2 | 2 4 5 \ | 6 1 3 | 4 вставлена между 2 и 5 |
| 3 | 2 4 5 6 \ | 1 3 | 6 остаётся на месте |
| 4 | 1 2 4 5 6 \ | 3 | 1 сдвигает весь префикс |
| 5 | 1 2 3 4 5 6 | 3 вставлена между 2 и 4 |
Вертикальной чертой условно отделена отсортированная часть.
¶Свойства и оценка сложности
- Временная сложность. В худшем случае (обратно упорядоченный массив) число сравнений и сдвигов составляет порядка n²/2, то есть O(n²). В среднем — также O(n²). В лучшем случае (уже отсортированный массив) каждое сравнение сразу показывает, что сдвиг не нужен, и сложность линейна — O(n).
- Пространственная сложность. O(1): сортировка выполняется «на месте».
- Устойчивость. Алгоритм устойчив: равные элементы сохраняют взаимный порядок, поскольку вставка происходит только после строго больших элементов.
- Адаптивность. Время работы зависит от исходной упорядоченности: чем ближе массив к отсортированному, тем быстрее завершение.
- Онлайн-режим. Алгоритм способен сортировать данные по мере их поступления, не требуя наличия всего массива заранее.
Число операций записи в память у сортировки вставками относительно невелико: каждый элемент перемещается в среднем на половину длины префикса, что делает её предпочтительной в задачах, где запись дороже чтения.
¶Место среди алгоритмов сортировки
Сортировка вставками — один из трёх классических простых алгоритмов наряду с сортировкой выбором и сортировкой пузырьком. По сравнению с ними она обычно эффективнее на практике: число сравнений в среднем вдвое меньше, чем у сортировки выбором, а число обменов — заметно меньше, чем у пузырьковой. Однако при больших n все они проигрывают быстрым алгоритмам — быстрой сортировке, сортировке слиянием, пирамидальной сортировке, имеющим сложность O(n log n).
Родственные усовершенствования:
- Сортировка Шелла — обобщение, при котором сначала сортируются подпоследовательности с большим шагом, что снижает итоговое число сдвигов.
- Бинарная сортировка вставками — позиция вставки ищется двоичным поиском, что уменьшает число сравнений, но не число сдвигов.
- Сортировка вставками в связном списке — вариант, где вставка не требует сдвига элементов.
¶Применение
Благодаря простоте и хорошему поведению на малых и почти отсортированных массивах сортировка вставками широко используется как вспомогательный приём:
- в гибридных алгоритмах — например, в вариантах быстрой сортировки и сортировки слиянием подмассивы длиной примерно до 10–16 элементов досортировываются вставками;
- в стандартных библиотеках: функция сортировки в ряде реализаций переключается на вставки для коротких диапазонов;
- во встраиваемых системах и там, где объём данных мал, а накладные расходы на рекурсию нежелательны;
- в задачах инкрементальной сортировки, когда в уже упорядоченный набор добавляются новые элементы;
- в учебных курсах как базовый пример анализа алгоритмов, инвариантов циклов и асимптотических оценок.
¶Реализация
Типичная реализация на псевдокоде:
`` for i от 1 до n-1: key = a[i] j = i - 1 пока j >= 0 и a[j] > key: a[j+1] = a[j] j = j - 1 a[j+1] = key ``
В языках программирования алгоритм записывается в несколько строк; в Python, например, внутренний цикл может быть выражен через сдвиг среза, а в C — через обычный цикл while с индексами. Корректность доказывается инвариантом: перед каждой итерацией внешнего цикла первые i элементов массива упорядочены и содержат те же значения, что и исходные.
¶Достоинства и недостатки
Достоинства: простота реализации и понимания, устойчивость, работа на месте, линейное время на почти отсортированных данных, малый объём кода, естественная обработка потоковых данных.
Недостатки: квадратичная сложность на больших неупорядоченных массивах, большое число сдвигов при обратном порядке, непригодность для сортировки крупных наборов данных без гибридных схем.
Источники: Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»; Кнут Д. «Искусство программирования», том 3; Седжвик Р. «Фундаментальные алгоритмы на C».