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

Что такое сортировка вставками

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

Метод прост в понимании и эффективен на почти упорядоченных данных, поэтому его часто изучают первым среди сортировок.

Идея алгоритма

В начале считаем, что первый элемент уже «отсортирован». Затем берём второй элемент и двигаем его влево, пока слева стоят большие значения. Повторяем для третьего, четвёртого и так до конца массива. На каждом шаге отсортированная часть слева увеличивается на один элемент.

нач цел A[1:N], i, j, x нц для i от 2 до N x := A[i] j := i - 1 нц пока j >= 1 и A[j] > x A[j+1] := A[j] j := j - 1 кц A[j+1] := x кц кон

Разбор шагов на примере

Шаг	Состояние массива
исходный	5 2 4 1
вставили 2	2 5 4 1
вставили 4	2 4 5 1
вставили 1	1 2 4 5

Правило: на каждом шаге часть массива слева от текущего элемента уже отсортирована. Мы лишь находим место для очередного значения и сдвигаем большие элементы вправо, освобождая ячейку.

Скорость работы

В худшем случае (массив отсортирован в обратном порядке) число сравнений растёт примерно как квадрат длины массива: каждый новый элемент приходится двигать в самое начало. Зато на уже почти упорядоченных данных метод работает очень быстро — почти за один проход, ведь внутренний цикл почти не выполняется.

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

Сравнение с другими методами

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

Частые ошибки: выход за левую границу массива (нужна проверка j >= 1); потеря вставляемого значения, если не сохранить его в переменную x; неверный порядок условий в цикле «пока».

Кратко о главном

• Элементы вставляются по одному в отсортированную левую часть.
• Большие значения сдвигаются вправо, освобождая место.
• Метод быстр на почти упорядоченных данных.
• В худшем случае время растёт как квадрат длины массива.