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

Сортировка вставками (insertion sort) — алгоритм сортировки, на каждом шаге вставляющий очередной элемент из несортированной части на правильную позицию в уже отсортированную часть; сложность O(n^2) в среднем, O(n) для почти отсортированных данных.

Зачем нужно

Несмотря на O(n^2) в среднем, Insertion Sort практически применима для малых массивов (n < 30) и почти отсортированных данных, где показывает O(n). Именно поэтому TimSort (гибрид Merge Sort + Insertion Sort, используемый в Python и Java) применяет Insertion Sort для небольших блоков. Понимание алгоритма формирует интуицию для более сложных сортировок.

Где используется

  • Маленькие массивы (n < 30) — лучше Quick Sort из-за малых констант
  • Почти отсортированные данные (online sorting): элементы поступают по одному
  • TimSort: Insertion Sort для блоков размером 32–64
  • Карточные игры: как человек сортирует карты в руке

Основной контент

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

Массив: [5, 3, 8, 1, 2]

Шаг 1: [5] | 3, 8, 1, 2  → вставляем 3: [3, 5] | 8, 1, 2
Шаг 2: [3, 5] | 8, 1, 2  → вставляем 8: [3, 5, 8] | 1, 2
Шаг 3: [3, 5, 8] | 1, 2  → вставляем 1: [1, 3, 5, 8] | 2
Шаг 4: [1, 3, 5, 8] | 2  → вставляем 2: [1, 2, 3, 5, 8]

Реализация

function insertionSort(arr) {
  const a = [...arr]; // не мутируем оригинал
  for (let i = 1; i < a.length; i++) {
    const key = a[i]; // текущий элемент для вставки
    let j = i - 1;
    // Сдвигаем вправо элементы больше key
    while (j >= 0 && a[j] > key) {
      a[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key; // вставляем на правильную позицию
  }
  return a;
}

console.log(insertionSort([5, 3, 8, 1, 2]));
// [1, 2, 3, 5, 8]

// In-place вариант
function insertionSortInPlace(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) arr[j + 1] = arr[j--];
    arr[j + 1] = key;
  }
  return arr;
}

Сложность

Случай Время Память
Best case O(n) O(1)
Average case O(n^2) O(1)
Worst case O(n^2) O(1)

Best case — уже отсортированный массив: внутренний while не выполняется. Worst case — обратно отсортированный: каждый элемент проходит весь путь влево.

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

Алгоритм Лучший случай Стабильная In-place
Insertion Sort O(n) Да Да
Selection Sort O(n^2) Нет Да
Bubble Sort O(n) с оптимизацией Да Да

Insertion Sort предпочтительнее Selection Sort почти всегда: лучший случай O(n) и стабильная.

Бинарная вставка (Binary Insertion Sort)

// Используем бинарный поиск для нахождения позиции — O(log n) сравнений
// Но сдвиг всё равно O(n), поэтому общая сложность не улучшается
function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let lo = 0, hi = i;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (arr[mid] <= key) lo = mid + 1;
      else hi = mid;
    }
    // lo — позиция вставки; сдвигаем элементы
    arr.copyWithin(lo + 1, lo, i); // arr.splice(lo, 0, key) — O(n)
    arr[lo] = key;
  }
  return arr;
}

Частые ошибки

  • Забывать сохранять key = arr[i] до начала сдвига — теряем значение, которое затирается сдвигом.
  • Использовать swap вместо сдвига — Insertion Sort с swap работает, но делает лишние операции.
  • Применять для больших несортированных массивов (n > 1000) там, где Quick Sort на порядки быстрее.

Связанные темы

Ресурсы