Skip to main content

Як працює швидке сортування (сортування Хоара)?

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

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

  • Швидке сортування (Хоара) - алгоритм «розділяй і володарюй»: обираємо опорний елемент (pivot), переставляємо елементи так, щоб зліва були ≤ pivot, справа ≥ pivot (розбиття Хоара), потім рекурсивно сортуємо обидві частини.
  • Складність: у середньому O(n log n), найгірший випадок O(n²) (за невдалого вибору pivot), пам'ять O(log n) за рахунок глибини рекурсії. Алгоритм in-place і нестабільний.

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

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

Швидке сортування - класичний алгоритм сортування на місці. Ключова ідея: обрати pivot і «розбити» масив на дві частини так, щоб усі елементи зліва не перевищували pivot, а справа не були меншими за pivot. Потім незалежно відсортувати ліву і праву частини. Схема Хоара - конкретний спосіб такого розбиття з двома «бігунками» з кінців масиву.

Схема Хоара: кроки

  1. Обрати опорний елемент pivot (наприклад, середній за індексом або за правилом median-of-three).
  2. Поставити два вказівники: i = low - 1 і j = high + 1.
  3. Рухати i вправо, поки A[i] < pivot. Рухати j вліво, поки A[j] > pivot.
  4. Якщо i ≥ j - повернути j як індекс розбиття (останній індекс лівої частини).
  5. Інакше обміняти A[i] і A[j] і продовжувати.
  6. Після розбиття рекурсивно викликати сортування для [low..j] і [j+1..high].

Псевдокод (розбиття Хоара)

partition_hoare(A, low, high): pivot := A[(low + high) // 2] i := low - 1 j := high + 1 while true: repeat i := i + 1 until A[i] >= pivot repeat j := j - 1 until A[j] <= pivot if i >= j: return j // індекс, що розділяє масив на [low..j] і [j+1..high] swap A[i], A[j] quicksort(A, low, high): if low >= high: return p := partition_hoare(A, low, high) quicksort(A, low, p) quicksort(A, p + 1, high)

Реалізація на JavaScript (схема Хоара)

function partitionHoare(a, low, high) { const pivot = a[Math.floor((low + high) / 2)]; let i = low - 1; let j = high + 1; while (true) { do { i++; } while (a[i] < pivot); do { j--; } while (a[j] > pivot); if (i >= j) return j; // j - межа лівої частини [a[i], a[j]] = [a[j], a[i]]; } } function quicksort(a, low = 0, high = a.length - 1) { if (low >= high) return a; const p = partitionHoare(a, low, high); quicksort(a, low, p); quicksort(a, p + 1, high); return a; } // Приклад: const arr = [9, 3, 7, 1, 8, 2, 5]; console.log(quicksort(arr)); // [1, 2, 3, 5, 7, 8, 9]

Важливо: межі рекурсії при схемі Хоара

partitionHoare повертає індекс p, такий що ліва частина - це [low..p], права - [p+1..high]. Помилка «quicksort(a, low, p - 1)» призводить до пропуску елементів і/або зациклення.

Приклад розбиття (коротко)

Для масиву [9, 3, 7, 1, 8, 2, 5], pivot = середній за індексом (7). i рухається вправо до 9 (стоп, 9 ≥ 7), j вліво до 5 (стоп, 5 ≤ 7). Міняємо 9 ↔ 5 → [5, 3, 7, 1, 8, 2, 9]. Далі i зупиниться на 7, j на 2 - міняємо → [5, 3, 2, 1, 8, 7, 9]. Потім i перетне j - p вказує на кінець лівої частини. Далі рекурсивні виклики сортують підмасиви.

Вибір опорного елемента (pivot)

  • Перший/останній елемент - просто, але погано на вже відсортованих масивах (найгірший випадок).
  • Випадковий pivot - знижує ймовірність найгіршого випадку до рідкісної.
  • Median-of-three (медіана з першого/середнього/останнього) - проста евристика проти деградації на частково відсортованих даних.

Складність

  • Середня: O(n log n) - при збалансованих розбиттях.
  • Найгірша: O(n²) - за сильного дисбалансу (наприклад, уже відсортований масив і поганий pivot).
  • Пам'ять: O(log n) - глибина рекурсії в середньому (у найгіршому - O(n)).

Стабільність і властивості

  • In-place: не потребує дод. пам'яті під масив (окрім стека викликів).
  • Нестабільна: відносний порядок рівних елементів не зберігається.
  • Чутлива до вибору pivot; для великої кількості дублікатів краще 3-путьове розбиття.

Дублікати і 3-путьове розбиття (пришвидшує за великої кількості рівних)

Замість класичного 2-путьового розбиття можна ділити на три зони: < pivot, = pivot, > pivot. Це зменшує глибину рекурсії за великої кількості дублікатів.

function quicksort3way(a, low = 0, high = a.length - 1) { if (low >= high) return a; const pivot = a[Math.floor((low + high) / 2)]; let lt = low, i = low, gt = high; while (i <= gt) { if (a[i] < pivot) { [a[lt], a[i]] = [a[i], a[lt]]; lt++; i++; } else if (a[i] > pivot) { [a[i], a[gt]] = [a[gt], a[i]]; gt--; } else { i++; } } quicksort3way(a, low, lt - 1); quicksort3way(a, gt + 1, high); return a; }

Ітеративна версія (без рекурсії)

function quicksortIterative(a) { const stack = [[0, a.length - 1]]; while (stack.length) { const [low, high] = stack.pop(); if (low >= high) continue; const p = partitionHoare(a, low, high); // Спочатку обробляємо менший підмасив (евристика для зниження глибини стека) if (p - low < high - (p + 1)) { stack.push([p + 1, high]); stack.push([low, p]); } else { stack.push([low, p]); stack.push([p + 1, high]); } } return a; }

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

  • Неправильні межі рекурсії для схеми Хоара: потрібно сортувати [low..p] і [p+1..high].
  • Плутанина між Хоара і Ломуто (у Ломуто pivot зазвичай у кінці і повертається позиція pivot; у Хоара pivot не обов'язково опиняється на «своєму» місці після partition).
  • Вибір поганого pivot (наприклад, перший елемент) на майже відсортованих даних → деградація до O(n²).
  • Помилки з індексами i/j (off-by-one), неправильні умови зупинки і порівняння.

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

  • Сортування загального призначення для чисел/порівнюваних об'єктів у пам'яті, коли стабільність не критична.
  • За великої кількості дублікатів - розглянути 3-путьове розбиття або гібрид (introsort).

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

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

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

Запропонувати правку