Алгоритм Хоара – вибірка медиани

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

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

Алгоритм Хоара шукає елемент, що розташований посередині сортування масиву, без того щоб повністю його упорядкувати. Він працює шляхом рекурсивного розділення масиву на частини, де шуканий елемент зберігається у певному підмасиві.

Аналогія

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

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

• Потрібно знайти середнє значення у великому масиві без сортування.
• Дані не повинні бути вже відсортованими.
• Потрібна швидка оцінка середнього значення, а не точне сортування.
• Коли розмір масиву великий і час сортування критичний.
• При роботі з потоками даних, де можна обробляти частини масиву окремо.

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

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

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

[7, 2, 5, 3, 9]   // вибираємо пивот = 7
↓
[2, 5, 3] | 7 | [9]
   ↑          ↓
[2, 5, 3]    // позиція пивоту = 3 (0‑індекс)

Складність

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

Код (js)

// Функція для вибору медиани за алгоритмом Хоара
function quickSelectMedian(arr) {
  // Перевірка, що масив не порожній
  if (!Array.isArray(arr) || arr.length === 0) return null;

  // Кількість елементів, за якою шукаємо медиану (0‑індекс)
  const k = Math.floor((arr.length - 1) / 2);

  // Внутрішня рекурсивна функція, що працює на ділянці масиву
  function select(left, right, kIndex) {
    // Якщо ділянка містить один елемент – це наш результат
    if (left === right) return arr[left];

    // Вибираємо пивот – середній елемент ділянки
    const pivotIndex = Math.floor((left + right) / 2);
    const pivotValue = arr[pivotIndex];

    // Переміщуємо пивот у кінець ділянки для простішого розділення
    [arr[pivotIndex], arr[right]] = [arr[right], arr[pivotIndex]];

    // Підготовка до розділення: i – позиція для менших елементів
    let storeIndex = left;
    for (let i = left; i < right; i++) {
      // Якщо елемент менший за пивот, переміщаємо його ліворуч
      if (arr[i] < pivotValue) {
        [arr[storeIndex], arr[i]] = [arr[i], arr[storeIndex]];
        storeIndex++;
      }
    }

    // Повертаємо пивот на його остаточну позицію
    [arr[storeIndex], arr[right]] = [arr[right], arr[storeIndex]];

    // Тепер storeIndex – позиція пивота у відсортованому вигляді
    if (kIndex === storeIndex) {
      return arr[storeIndex];
    } else if (kIndex < storeIndex) {
      // Шукаємо у лівій частині
      return select(left, storeIndex - 1, kIndex);
    } else {
      // Шукаємо у правій частині
      return select(storeIndex + 1, right, kIndex);
    }
  }

  // Запускаємо рекурсію на всьому масиві
  return select(0, arr.length - 1, k);
}

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

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

1. Вибір поганого пивота – використання першого елемента може призвести до O(n²). Рекомендується вибирати середній або випадковий елемент.
2. Неправильне оновлення індексу k – при переході в праву частину треба коригувати k, додаючи розмір лівої частини +1.
3. Модифікація вхідного масиву – якщо потрібно зберегти оригінал, робіть копію перед викликом.
4. Перевірка порожнього масиву – без цього функція поверне undefined.
5. Оптимізація – для дуже великих масивів можна застосувати «median‑of‑medians» для гарантованої O(n) складності.

Перевір себе

1. Яка середня складність алгоритму Хоара для вибору медиани?
2. Чому важливо коригувати індекс k при переході в праву частину?