Код (простая in‑place реализация с Lomuto‑partition и случайным опорным элементом):
function quicksort(arr, left = 0, right = arr.length - 1) {
if (left >= right) return;
// случайный опорный элемент — уменьшает шанс худшего случая
const p = left + Math.floor(Math.random() * (right - left + 1));
[arr[p], arr[right]] = [arr[right], arr[p]];
const pivot = arr[right];
let i = left;
for (let j = left; j < right; j++) {
if (arr[j] < pivot) {
[arr[i], arr[j]] = [arr[j], arr[i]];
i++;
}
}
[arr[i], arr[right]] = [arr[right], arr[i]];
quicksort(arr, left, i - 1);
quicksort(arr, i + 1, right);
}
Анализ производительности и памяти:
- Время (количественные оценки):
- лучший случай: $O(n\log n)$ — когда опорный элемент постоянно делит массив примерно пополам.
- средний (ожидаемый) случай: $O(n\log n)$ — при случайном или «хорошем» выборе опорных элементов.
- худший случай: $O(n^2)$ — когда каждый раз получается сильно неравное разбиение (например, опора — минимум или максимум в уже отсортированном массиве).
- Пространство:
- дополнительная память (вне входного массива и вызовов): $O(1)$ для in‑place версии (Lomuto/Hoare).
- стек рекурсии: в среднем $O(\log n)$, в худшем случае $O(n)$ (при глубокой неравномерной рекурсии).
Как выбор опорного элемента влияет на производительность:
- фиксированный выбор (например, всегда первый/последний элемент) делает алгоритм уязвимым к уже отсортированным или почти отсортированным входам → частые плохие разбиения → худший случай $O(n^2)$.
- случайный выбор опоры (как в коде) даёт вероятностную гарантию: ожидаемое время $O(n\log n)$, очень малый шанс встретить худший случай.
- медиана из трёх (median‑of‑three) уменьшает вероятность плохих разбиений на «упорядоченных» входах и обычно ускоряет на практике.
- три‑путёвое (3‑way) разбиение (Dutch national flag) полезно при множественных равных элементах — при большом числе одинаковых ключей это даёт выигрыш (в крайних случаях приводит к близкому к $O(n)$ времени на равных элементах).
- чтобы получить гарантию худшего случая $O(n\log n)$, используют гибриды (introsort): при слишком большой глубине рекурсии алгоритм переключается на heapsort.
Короткое резюме:
- QuickSort — быстрый в среднем: $O(n\log n)$;
- но опасен на худших входах: $O(n^2)$;
- правильный выбор опоры (рандомизация, median‑of‑three, 3‑way) и/или гибрид с heap/intro делает его надёжным и эффективным на практике;
- память: in‑place — $O(1)$ + стек $O(\log n)$ в среднем, $O(n)$ в худшем.