Сортировка вставками
💻 Информатика · 9 класс
Как работает сортировка вставками: упорядочивание массива по одному элементу за шаг.
Что такое сортировка вставками
Сортировка вставками — это способ упорядочить массив, при котором мы по очереди берём каждый элемент и вставляем его на правильное место среди уже отсортированных слева элементов. Так обычно человек раскладывает по порядку карты в руке: берёт новую карту и вставляет её между нужными.
Метод прост в понимании и эффективен на почти упорядоченных данных, поэтому его часто изучают первым среди сортировок.
Идея алгоритма
В начале считаем, что первый элемент уже «отсортирован». Затем берём второй элемент и двигаем его влево, пока слева стоят большие значения. Повторяем для третьего, четвёртого и так до конца массива. На каждом шаге отсортированная часть слева увеличивается на один элемент.
нач
цел 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; неверный порядок условий в цикле «пока».
Кратко о главном
- Элементы вставляются по одному в отсортированную левую часть.
- Большие значения сдвигаются вправо, освобождая место.
- Метод быстр на почти упорядоченных данных.
- В худшем случае время растёт как квадрат длины массива.