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

Сортировка вставками — это то, как большинство людей раскладывают карты в руке: берут следующую карту и вставляют её на нужное место среди уже упорядоченных карт. Она медленная на длинных случайных списках, но очень быстрая на коротких или почти отсортированных, поэтому настоящие библиотеки сортировки до сих пор её используют.

Сортируемые столбики: слева отсортированная часть, и один столбик сдвигается в неё назад мимо больших столбиков
Сортируемые столбики: слева отсортированная часть, и один столбик сдвигается в неё назад мимо больших столбиков

Идея

Держите начало списка отсортированным. Вначале эта отсортированная часть — только первое значение. Возьмите следующее значение и сравните его с предыдущим. Если предыдущее больше, поменяйте их местами и сравните снова, на одно место дальше назад. Остановитесь, когда предыдущее значение не больше или когда значение дошло до начала. Отсортированная часть выросла на одно значение. Повторяйте с каждым значением до конца.

Пример

Возьмём 5, 1, 4, 2, 8. Проход 1 берёт 1: 5 больше, меняем местами, и 1 доходит до начала: 1, 5, 4, 2, 8. Проход 2 берёт 4: оно меняется местами с 5, затем останавливается на 1: 1, 4, 5, 2, 8. Проход 3 берёт 2: оно меняется местами с 5 и с 4, затем останавливается на 1: 1, 2, 4, 5, 8. Проход 4 берёт 8, которое уже больше 5, так что хватает одного сравнения. Итого 7 сравнений и 4 обмена. Сортировке пузырьком на том же списке нужно 9 сравнений, сортировке выбором — 10.

Обменов столько же, сколько инверсий

Инверсия — это пара значений в неправильном порядке. Обмен двух соседей, стоящих в неправильном порядке, убирает ровно одну инверсию, а сортировка вставками меняет местами только таких соседей. Значит, она делает ровно столько обменов, сколько инверсий в начальном списке, — столько же, сколько сортировка пузырьком. Кроме того, каждый проход делает не больше одного сравнения, которое не ведёт к обмену: того, что его останавливает. Поэтому сравнений столько, сколько инверсий, плюс не больше n − 1.

Адаптивность: быстро, когда список почти отсортирован

Поскольку работа равна числу инверсий плюс примерно n, сортировка вставками быстра всякий раз, когда инверсий мало. Отсортированному списку нужно n − 1 сравнений и ни одного обмена. Список, где каждое значение стоит всего в нескольких местах от своего, сортируется за время, близкое к n. Только список, далёкий от отсортированного, например обратный с n(n − 1)/2 инверсиями, требует времени, пропорционального n². На случайном списке в среднем получается около n²/4 обменов.

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

Сортировка вставками устойчива, не требует дополнительной памяти и имеет очень малые накладные расходы. На коротких списках она обгоняет алгоритмы, которые быстрее на бумаге. Многие библиотечные сортировки, например Timsort в Python и Java и introsort в C++, переключаются на сортировку вставками для небольших кусков списка, обычно до нескольких десятков значений. Она также подходит для данных, которые поступают по одному значению, потому что каждое новое значение можно вставить сразу, как только оно пришло.

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

Откройте приложение и нажмите «Пуск» или «Шаг», чтобы идти по одному сравнению. Вставляемое значение выделено своим цветом, значение, с которым его сравнивают, подсвечено, а отсортированная часть зелёная. В отличие от сортировки пузырьком и сортировки выбором, зелёная часть не окончательна: более позднее и меньшее значение ещё может встать в неё. Попробуйте почти отсортированный список, чтобы увидеть, какие короткие проходы, а затем обратный.

Часто задаваемые вопросы

Какова временная сложность сортировки вставками?

O(n²) в худшем и среднем случае и O(n) в лучшем, когда список уже отсортирован. Точнее, время пропорционально n плюс число инверсий. Дополнительной памяти нужно всего O(1).

Чем сортировка вставками отличается от сортировки выбором?

Сортировка выбором просматривает всю неотсортированную часть, чтобы найти наименьшее значение, поэтому всегда делает n(n − 1)/2 сравнений, но мало обменов. Сортировка вставками берёт следующее значение как есть и сдвигает его назад ровно настолько, насколько нужно, поэтому делает меньше сравнений, особенно на почти отсортированных списках, но больше обменов.

Что такое сортировка двоичными вставками?

Вариант, который находит место нового значения двоичным поиском в отсортированной части, примерно за log n сравнений, а не за n. Значения всё равно нужно сдвигать, чтобы освободить место, поэтому число перемещений и худший случай O(n²) не меняются.

Устойчива ли сортировка вставками?

Да. Значение сдвигается назад только мимо строго больших значений, поэтому равные значения сохраняют исходный порядок.

Готовы попробовать?

Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

Попробовать сортировку вставками