Сортировка вставками
Берём следующее значение и вставляем его в отсортированный префикс. Больших соседей сдвигаем на одну позицию вправо, пока не найдётся место для ключа.
До 24 значений. Попробуйте повторы или отрицательные числа.
Шаг 0 / 27: Исходный массив. Первый элемент начинает отсортированный префикс.
Массив: [5, 2, 4, 2, 1]
Сравнения: 0 · Записи: 0
Зелёный — отсортированный префикс. Фиолетовый — извлечённый ключ. Подсвеченные столбцы — текущая операция. Позиции считаются с нуля.
Что остаётся отсортированным
Перед каждой вставкой обработанный префикс отсортирован. Ключ временно хранится вне массива, оставляя пустую ячейку. Каждый сдвиг перемещает эту ячейку влево; вставка заполняет её и расширяет отсортированный префикс.
Почему сортировка стабильна
Равные значения не перемещаются друг через друга: условие использует >, а не >=. В [5, 2, 4, 2, 1] первая двойка останется перед второй. AlgiViz сохраняет id исходной позиции каждого элемента.
Сложность
- Уже отсортированный вход
- O(n)
- Средний и худший случай
- O(n²)
- Дополнительная память самого алгоритма
- O(1)
Визуализатор хранит полную историю состояний. Её память — O(n × число шагов), до O(n³) в этой реализации. Это отдельные затраты, отличные от памяти самой сортировки.
Реализация на JavaScript
Эта обёртка копирует вход перед сортировкой, поэтому показанная функция дополнительно использует O(n) памяти.
function insertionSort(values) {
const result = [...values];
for (let i = 1; i < result.length; i++) {
const key = result[i];
let j = i - 1;
while (j >= 0 && result[j] > key) {
result[j + 1] = result[j];
j--;
}
result[j + 1] = key;
}
return result;
}Видеоразбор
Работает на AlgiViz
Алгоритм сортировки вставками определён на этом сайте. AlgiViz предоставляет неизменяемые состояния операций с массивом, временную шкалу и canvas-отрисовку. Запись видео — отдельный пакет CanvasTake; экспорт к этой странице пока не подключён.