Запропонувати правкуПокращити цю статтюДопрацюйте відповідь до «Як працює швидке сортування (сортування Хоара)?». Ваші зміни проходять модерацію перед публікацією.Потрібне підтвердженняКонтентЩо ви змінюєте🇺🇸EN🇺🇦UAПереглядЗаголовок (UA)Коротка відповідь (UA)- Швидке сортування (Хоара) - алгоритм «розділяй і володарюй»: обираємо опорний елемент (pivot), переставляємо елементи так, щоб зліва були ≤ pivot, справа ≥ pivot (розбиття Хоара), потім рекурсивно сортуємо обидві частини. - Складність: у середньому O(n log n), найгірший випадок O(n²) (за невдалого вибору pivot), пам'ять O(log n) за рахунок глибини рекурсії. Алгоритм in-place і нестабільний.Показується над повною відповіддю для швидкого нагадування.Відповідь (UA)Зображення## Коротка відповідь - Швидке сортування (Хоара) - алгоритм «розділяй і володарюй»: обираємо опорний елемент (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).Для рев’юераПримітка для модератора (необов’язково)Бачить лише модератор. Прискорює рев’ю.