Быстрая сортировка (Quick sort)
Один из самых популярных и быстрых на практике алгоритмов сортировки на основе стратегии «разделяй и властвуй».
Идея алгоритма
Выбирается опорный элемент (pivot). Массив разделяется на элементы меньше опорного и больше (или равные). Затем эти подмассивы рекурсивно сортируются тем же методом. В итоге весь массив оказывается отсортированным.
Асимптотика:
- Время (средний случай): O(n log n)
- Время (худший случай — неудачный выбор опорного): O(n²)
- Память: в среднем O(log n) за счёт стека рекурсии
- Обычно не является стабильной сортировкой
Когда использовать
- Для больших массивов в реальных приложениях;
- Когда важна скорость и можно пожертвовать стабильностью;
- Когда данные расположены случайно, без особой структуры.
Плюсы
- Очень быстрая на практике при хорошем выборе опорного элемента;
- Работает in-place, не требует много памяти;
- Проста для оптимизаций и гибридных решений.
Минусы
- Худший случай — O(n²);
- Не является стабильной сортировкой;
- При неудачном выборе опорного может сильно замедлиться.
Пример кода
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[Math.floor(arr.length / 2)];
const left = [];
const right = [];
const equal = [];
for (const x of arr) {
if (x < pivot) left.push(x);
else if (x > pivot) right.push(x);
else equal.push(x);
}
return [...quickSort(left), ...equal, ...quickSort(right)];
}Попробуй самостоятельно написать алгоритм, а затем сравнить
Полезные темы
Рекомендуем изучить эти темы для лучшего понимания