Що таке сортування вставками (insertion sorts)?

АлгоритмиJunior~3 хв читання

Коротка відповідь

Сортування вставками (Insertion Sort) - це простий, стабільний і «внутріпроцедурний» (in-place) алгоритм, який формує відсортовану частину масиву, послідовно вставляючи кожен наступний елемент на своє місце. У гіршому і середньому випадках працює за O(n²), у найкращому випадку (майже відсортовані дані) - за O(n). Підходить для малих масивів, майже відсортованих даних і як частина гібридних алгоритмів.

Детальний розбір

Ідея алгоритму

Уявіть, що ви розкладаєте карти за зростанням у руці: берете нову карту і вставляєте її у вже відсортовану частину так, щоб порядок зберігався. Так само алгоритм проходить масив зліва направо, підтримуючи зліва відсортований префікс і вставляючи в нього поточний елемент.

Покроковий алгоритм

Вважаємо, що підмасив з одного елемента (перший) уже відсортований.
Беремо наступний елемент (ключ) і порівнюємо його з елементами відсортованої частини справа наліво.
Зсуваємо елементи, більші за ключ, на одну позицію вправо, щоб звільнити місце.
Вставляємо ключ на звільнену позицію.
Повторюємо для всіх елементів.

Приклад коду (JavaScript)

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    // Зсуваємо елементи вправо, поки вони більші за key
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    // Вставляємо key на свою позицію
    arr[j + 1] = key;
  }
  return arr;
}

// Оптимізація: бінарна вставка (менше порівнянь, зсуви ті самі)
function binaryInsertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let left = 0;
    let right = i; // напівінтервал [left, right)

    // Знаходимо позицію вставки бінарним пошуком
    while (left < right) {
      const mid = (left + right) >> 1;
      // <= ставить key після рівних - зберігає стабільність
      if (arr[mid] <= key) left = mid + 1; else right = mid;
    }

    // Зсув блоку вправо на 1, щоб вставити key
    for (let j = i; j > left; j--) arr[j] = arr[j - 1];
    arr[left] = key;
  }
  return arr;
}

// Демонстрація
const nums = [5, 2, 4, 6, 1, 3];
console.log(insertionSort([...nums]));        // [1,2,3,4,5,6]
console.log(binaryInsertionSort([...nums]));  // [1,2,3,4,5,6]

Складність і властивості

Час: у гіршому/середньому випадках O(n²), у найкращому - O(n) при майже відсортованих даних (мало інверсій).
Пам'ять: O(1) додаткової (in-place).
Стабільність: стабільне сортування (рівні елементи зберігають відносний порядок).
Адаптивність: швидше працює на майже відсортованих масивах; фактично час залежить від кількості інверсій.
Онлайн-властивість: можна підтримувати відсортовану структуру, вставляючи елементи, що надходять, по одному.

Коли використовувати

Малі масиви (зазвичай до 20-50 елементів) - низькі константи й простота.
Майже відсортовані дані - близько до O(n).
У гібридних сортуваннях: як «доведення» для малих підмасивів після розбиття (наприклад, після швидкого сортування).
Онлайн-оновлення відсортованих колекцій, коли елементи надходять поступово.

Варіанти та оптимізації

Бінарна сортування вставками: зменшує кількість порівнянь з O(n²) до O(n log n), але зсувів усе одно O(n²).
Сентинел: заздалегідь ставлять мінімальний елемент на початок, щоб прибрати перевірки меж у циклі.
Зсуви замість обмінів: використовувати зсув блоку і одиничний запис ключа - менше операцій запису.
Зв'язні списки: вставки можуть бути O(1) за відомої позиції, але пошук позиції все одно O(n).
Зв'язок із Shell sort: Shell - це узагальнення вставок зі спадними «кроковими» інтервалами для зменшення кількості зсувів.

Порівняння з бульбашковим сортуванням і сортуванням вибором

Бульбашкове сортування vs вставки: обидва O(n²), але вставки зазвичай роблять менше зайвих обмінів і швидші на майже відсортованих масивах; бульбашкове можна оптимізувати до O(n) на відсортованому масиві, але константи вищі.
Вибір vs вставки: вибір робить O(n) обмінів, але завжди O(n²) порівнянь і не є стабільним (у класичному вигляді); вставки - стабільні й адаптивні.

Інваріант і коректність

Інваріант: після i-ї ітерації підмасив [0..i) відсортований. Вставка i-го елемента зберігає інваріант, оскільки всі елементи, більші за key, зсуваються, а key потрапляє на єдину відповідну позицію. Після завершення для i = n масив відсортований.

Часті помилки на співбесіді

Використання обмінів замість зсувів - більше записів і гірша продуктивність.
Помилки меж: не вставляють key після завершення циклу порівняння (потрібно arr[j + 1] = key).
Втрата стабільності: неправильно обрана умова порівняння при бінарній вставці.
Нерозуміння адаптивності: у найкращому випадку O(n), а не завжди O(n²).

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.