Insertion Sort (Сортировка вставками)
Краткое описание
Алгоритм сортировки, который строит отсортированный массив по одному элементу за раз, вставляя каждый новый элемент на правильное место в уже отсортированную часть. Аналогия: сортировка карт в руке. Эффективен на малых и почти отсортированных массивах, используется в гибридных алгоритмах.
Когда использовать
- Маленькие массивы — эффективна для малых наборов данных (обычно до 10-50 элементов) благодаря низким накладным расходам
- Почти отсортированные данные — лучший случай O(n) для уже или почти отсортированных массивов
- Онлайн-сортировка — идеальна для сортировки данных по мере их поступления
- Стабильная сортировка — сохраняет относительный порядок равных элементов
- Ограниченная память — использует O(1) дополнительной памяти
- Часть гибридных алгоритмов — используется как подпроцедура в продвинутых алгоритмах (Quick Sort, Merge Sort, TimSort, IntroSort) для малых подмассивов
Когда не стоит использовать:
- Большие массивы в случайном порядке — O(n²) сложность делает её неэффективной
- Данные в обратном порядке — худший случай O(n²), требует максимального количества сдвигов
С объяснением логики работы
/**
* Сортировка вставками (Insertion Sort)
* Принцип: разделяем массив на отсортированную (слева) и неотсортированную (справа) части.
* Берём элемент из неотсортированной части и вставляем его на правильное место в отсортированной части,
* сдвигая остальные элементы вправо. Как сортировка карт в руке.
*/
function insertionSort(arr) {
// Начинаем со второго элемента (индекс 1), так как первый элемент сам по себе уже "отсортирован"
// На каждой итерации граница между отсортированной и неотсортированной частью сдвигается вправо
for (let i = 1; i < arr.length; i++) {
// Сохраняем текущий элемент, который нужно вставить в отсортированную часть
// Это "карта", которую мы держим в руке и ищем для неё правильное место
let current = arr[i];
// j указывает на последний элемент отсортированной части (слева от current)
// Будем двигаться влево, сравнивая current с элементами отсортированной части
let j = i - 1;
// Сдвигаем элементы отсортированной части вправо, пока не найдём место для current
// Условия выхода из цикла:
// 1. j > -1: не вышли за границу массива слева
// 2. arr[j] > current: текущий элемент отсортированной части больше вставляемого
while (j >= 0 && arr[j] > current) {
// Сдвигаем элемент вправо, освобождая место для вставки
// Создаём "дыру", которая будет двигаться влево
arr[j + 1] = arr[j];
// Переходим к следующему элементу слева
j--;
}
// Когда цикл завершился, j указывает на элемент, который меньше или равен current
// (или j = -1, если current меньше всех элементов)
// Вставляем current на позицию j + 1 (сразу после меньшего элемента)
arr[j + 1] = current;
// Теперь отсортированная часть увеличилась на один элемент
// Элементы от arr[0] до arr[i] отсортированы
}
// Возвращаем отсортированный массив
// Массив сортируется "на месте" (in-place)
return arr;
}
// Пример использования
const numbers = [12, 11, 13, 5, 6];
console.log("Исходный массив:", numbers);
insertionSort(numbers);
console.log("Отсортированный массив:", numbers);
// Пример онлайн-сортировки (добавление элементов по одному)
const sorted = [1, 3, 5, 7];
// Добавляем элемент 4
sorted.push(4);
// Сортируем только новый элемент (один проход insertion sort)
let current = sorted[sorted.length - 1];
let j = sorted.length - 2;
while (j >= 0 && sorted[j] > current) {
sorted[j + 1] = sorted[j];
j--;
}
sorted[j + 1] = current;
console.log("Результат онлайн-сортировки:", sorted); // [1, 3, 4, 5, 7]С анализом сложностей
/**
* Сортировка вставками (Insertion Sort) с анализом сложности
*
* ВРЕМЕННАЯ СЛОЖНОСТЬ:
* - Лучший случай: O(n) — массив уже отсортирован, каждый элемент сравнивается только один раз
* - Средний случай: O(n²) — в среднем требуется n²/4 сравнений и n²/4 сдвигов
* - Худший случай: O(n²) — массив отсортирован в обратном порядке, максимум операций
*
* ПРОСТРАНСТВЕННАЯ СЛОЖНОСТЬ:
* - O(1) — требуется только константное количество памяти (i, j, current)
* - Сортировка происходит "на месте" (in-place)
*
* КОЛИЧЕСТВО ОПЕРАЦИЙ:
* - Сравнения (лучший): O(n-1) ≈ O(n)
* - Сравнения (худший): 1 + 2 + 3 + ... + (n-1) = n(n-1)/2 ≈ O(n²)
* - Сдвиги (лучший): O(0)
* - Сдвиги (худший): O(n²)
*
* ОСОБЕННОСТИ:
* - Адаптивный: O(n) на отсортированных данных, O(n + d) где d - число инверсий
* - Стабильный: сохраняет порядок равных элементов
* - Эффективен для малых массивов и онлайн-сортировки
*/
function insertionSort(arr) {
// Внешний цикл: выполняется (n-1) раз, где n = arr.length
// Начинаем с индекса 1, так как массив из одного элемента уже отсортирован
// Сложность внешнего цикла: O(n)
for (let i = 1; i < arr.length; i++) {
// Сохранение текущего элемента — O(1) операция
let current = arr[i];
// Инициализация j — O(1) операция
let j = i - 1;
// Внутренний цикл (while): количество итераций зависит от входных данных
//
// ЛУЧШИЙ СЛУЧАЙ (массив отсортирован):
// - Условие arr[j] > current сразу false
// - Цикл не выполняется (0 итераций)
// - Итого для всех итераций внешнего цикла: 0 + 0 + ... + 0 = 0 операций
// - Общая сложность: O(n) * O(1) = O(n)
//
// ХУДШИЙ СЛУЧАЙ (массив в обратном порядке):
// - Для элемента на позиции i нужно сравнить со всеми i предыдущими элементами
// - Итерация 1: 1 сравнение
// - Итерация 2: 2 сравнения
// - ...
// - Итерация n-1: (n-1) сравнений
// - Итого: 1 + 2 + ... + (n-1) = n(n-1)/2 ≈ n²/2 операций
// - Общая сложность: O(n²)
//
// СРЕДНИЙ СЛУЧАЙ (случайный порядок):
// - В среднем элемент проходит половину пути назад
// - Примерно n²/4 сравнений и n²/4 сдвигов
// - Общая сложность: O(n²)
while (j >= 0 && arr[j] > current) {
// Сдвиг элемента вправо — O(1) операция записи
//
// ВАЖНО: Insertion Sort выполняет много операций записи
// ЛУЧШИЙ СЛУЧАЙ: 0 сдвигов (массив отсортирован)
// ХУДШИЙ СЛУЧАЙ: n(n-1)/2 сдвигов (обратный порядок)
//
// Сравнение с другими алгоритмами по количеству записей:
// - Selection Sort: максимум n swap-операций (2n записей)
// - Bubble Sort: максимум n²/2 swap-операций (n² записей)
// - Insertion Sort: максимум n²/2 сдвигов (n²/2 записей)
arr[j + 1] = arr[j];
// Декремент — O(1)
j--;
}
// Вставка элемента на правильную позицию — O(1) операция
// Выполняется ровно (n-1) раз за всю работу алгоритма
arr[j + 1] = current;
// АДАПТИВНОСТЬ:
// Insertion Sort - адаптивный алгоритм, его производительность зависит от
// количества инверсий (пар элементов, стоящих в неправильном порядке).
// Формула: O(n + d), где d - количество инверсий
//
// Примеры:
// [1, 2, 3, 4, 5] - 0 инверсий → O(n)
// [1, 2, 4, 3, 5] - 1 инверсия → O(n + 1) ≈ O(n)
// [2, 1, 4, 3, 6, 5] - 3 инверсии → O(n + 3) ≈ O(n)
// [5, 4, 3, 2, 1] - 10 инверсий → O(n²)
}
// ИТОГОВАЯ СЛОЖНОСТЬ:
// Время: O(n) в лучшем, O(n²) в среднем и худшем
// Память: O(1) — только переменные i, j, current
//
// ПРЕИМУЩЕСТВА INSERTION SORT:
// 1. Эффективен на малых массивах (используется в TimSort, IntroSort)
// 2. O(n) на почти отсортированных данных
// 3. Стабильная сортировка
// 4. Онлайн-алгоритм (может сортировать данные по мере поступления)
// 5. Простая реализация
//
// СРАВНЕНИЕ С ДРУГИМИ O(n²) АЛГОРИТМАМИ:
// - Insertion Sort: лучший O(n), адаптивный, стабильный, хорош для почти отсортированных
// - Bubble Sort: лучший O(n), адаптивный, стабильный, много swap-операций
// - Selection Sort: всегда O(n²), не адаптивный, минимум swap-операций
return arr;
}
// Примеры для демонстрации разной сложности:
// ЛУЧШИЙ СЛУЧАЙ: O(n) — уже отсортирован
const best = [1, 2, 3, 4, 5];
// Выполнится: 4 сравнения, 0 сдвигов
// Каждый элемент сравнивается только с предыдущим один раз
// ХУДШИЙ СЛУЧАЙ: O(n²) — обратный порядок
const worst = [5, 4, 3, 2, 1];
// Выполнится: 1+2+3+4 = 10 сравнений, 10 сдвигов
// Каждый элемент проходит весь путь до начала массива
// СРЕДНИЙ СЛУЧАЙ: O(n²) — случайный порядок
const average = [3, 1, 4, 2, 5];
// Выполнится: примерно 5-7 сравнений, 5-7 сдвигов
// ПОЧТИ ОТСОРТИРОВАННЫЙ: O(n + d) где d - число инверсий
const nearSorted = [1, 2, 4, 3, 5, 6, 8, 7, 9];
// Всего 2 инверсии: (4,3) и (8,7)
// Выполнится: примерно 8 + 2 = 10 операций ≈ O(n)
// Очень эффективно! Быстрее чем O(n log n) алгоритмы
// ОНЛАЙН-СОРТИРОВКА: добавление элемента в отсортированный массив
// Это O(n) операция в худшем случае, но часто намного быстрее
const onlineSorted = [1, 3, 5, 7, 9];
// Добавляем элемент 6
onlineSorted.push(6);
// Вставка займёт O(log n) сравнений если использовать бинарный поиск
// или O(n) в худшем случае с линейным поиском