Сортування вставками (Insertion Sort)

Повне пояснення

Коротке пояснення

Insertion Sort проходить по масиву, беручи кожен елемент і вставляючи його у правильне місце серед вже відсортованих. Алгоритм базується на ідеї «вставки»: елемент переміщається ліворуч, поки не знайде місце, де попередній елемент менший.

Аналогія

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

Коли застосовувати

• Невеликий масив (до кількох тисяч елементів).
• Масив вже частково відсортований.
• Потрібна простота реалізації без додаткової пам’яті.
• Коли швидкість не критична, а зрозумілість важлива.

Кроки алгоритму

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

Візуальна інтуїція (текстова)

[5, 2, 4, 6, 1, 3]
   ^
Step 1: key=2, shift 5 right → [5,5,4,6,1,3]
Insert 2: [2,5,4,6,1,3]
   ^
Step 2: key=4, shift 5 right → [2,5,5,6,1,3]
Insert 4: [2,4,5,6,1,3]
   ^
Step 3: key=6, no shift → [2,4,5,6,1,3]
   ^
Step 4: key=1, shift 6,5,4,2 right → [2,2,4,5,6,3]
Insert 1: [1,2,4,5,6,3]
   ^
Step 5: key=3, shift 6,5,4 right → [1,2,4,4,5,6]
Insert 3: [1,2,3,4,5,6]

Складність

• Час: у найгіршому випадку O(n²), у середньому O(n²) при випадкових даних, у кращому — O(n) коли масив вже відсортований.
• Пам’ять: O(1), бо сортування виконується на місці без додаткових структур.

Код (js)

// Сортування вставками: простий, на місці алгоритм
function insertionSort(arr) {
  // Перевірка вхідних даних: масив з мінімум двома елементами
  if (!Array.isArray(arr) || arr.length < 2) return arr;

  // Проходимо по масиву, починаючи з другого елемента (індекс 1)
  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; // повертаємо відсортований масив
}

// Тестовий приклад
console.log(insertionSort([5, 2, 4, 6, 1, 3])); // очікуваний результат: [1,2,3,4,5,6]

Типові помилки і поради

1. Забуваєте про індекс 0 – починайте цикл з i = 1, а не 0.
2. Використовуєте arr.splice – це створює нові масиви і збільшує час.
3. Не перевіряєте вхід – якщо масив порожній, цикл не виконається, але варто явно повернути його.
4. Пам’ятайте про O(1) пам’ять – не створюйте додаткових масивів.
5. Оптимізація – для частково відсортованих даних можна додати прапорець, що зупиняє цикл, коли не було переміщень.

Перевір себе

1. Яка складність у найгіршому випадку для Insertion Sort?
2. Чи потребує алгоритм додаткової пам’яті, і якщо так, то скільки?