Что такое quick sort?
На этой странице
Quick sort - divide and conquer сортировка: выбирается pivot, элементы разделяются на меньшие и большие, затем части сортируются рекурсивно. В среднем работает за O(n log n), но в худшем случае может стать O(n^2).
Вопрос
Как работает quick sort, почему в худшем случае O(n²) и как выбирать опорный элемент?
Простая реализация
function quickSort(nums: number[]): number[] {
if (nums.length <= 1) return nums
const pivot = nums[nums.length - 1]
const left: number[] = []
const right: number[] = []
for (let i = 0; i < nums.length - 1; i++) {
if (nums[i] < pivot) left.push(nums[i])
else right.push(nums[i])
}
return [...quickSort(left), pivot, ...quickSort(right)]
}Эта версия понятная, но не in-place и создает много массивов.
Идея partition
Главный шаг quick sort - partition:
elements < pivot | pivot | elements >= pivotПосле partition pivot находится на правильном месте.
In-place версия (Lomuto partition)
Так quick sort пишут, когда просят не создавать новые массивы:
function quickSortInPlace(nums: number[], low = 0, high = nums.length - 1): number[] {
if (low >= high) return nums
const pivotIndex = partition(nums, low, high)
quickSortInPlace(nums, low, pivotIndex - 1)
quickSortInPlace(nums, pivotIndex + 1, high)
return nums
}
function partition(nums: number[], low: number, high: number): number {
const pivot = nums[high]
let boundary = low // все левее boundary - меньше pivot
for (let i = low; i < high; i++) {
if (nums[i] < pivot) {
;[nums[i], nums[boundary]] = [nums[boundary], nums[i]]
boundary++
}
}
;[nums[boundary], nums[high]] = [nums[high], nums[boundary]]
return boundary
}Partition для [7, 2, 9, 1, 5], pivot = 5:
i=0: 7 >= 5, пропускаем [7, 2, 9, 1, 5] boundary=0
i=1: 2 < 5, меняем с boundary [2, 7, 9, 1, 5] boundary=1
i=2: 9 >= 5, пропускаем [2, 7, 9, 1, 5] boundary=1
i=3: 1 < 5, меняем с boundary [2, 1, 9, 7, 5] boundary=2
ставим pivot на boundary [2, 1, 5, 7, 9] pivot на индексе 2Слева от 5 только меньшие, справа - большие. Дальше рекурсивно сортируем [2, 1] и [7, 9].
Сложность
Average:
O(n log n)Worst:
O(n^2)Worst case возникает при плохом выборе pivot, например если массив уже отсортирован, а pivot всегда крайний элемент. Тогда partition каждый раз отрезает только один элемент:
[1, 2, 3, 4, 5] pivot 5 -> [1, 2, 3, 4] и []
[1, 2, 3, 4] pivot 4 -> [1, 2, 3] и []
...Получается n уровней по n операций - O(n^2), и глубина рекурсии O(n).
Как выбирать pivot
- Случайный элемент - самый простой способ: плохой случай становится маловероятным на любых данных. Берем случайный индекс и меняем его с
nums[high]перед partition. - Медиана трех - берем медиану из первого, среднего и последнего элемента. Хорошо работает на почти отсортированных данных.
- Крайний элемент - годится для объяснения, но ломается на отсортированном input.
Еще одна ловушка - много одинаковых элементов: обычный partition отправляет их все в одну сторону. Решение - трехчастное разбиение (< pivot, = pivot, > pivot).
Что отвечать на собеседовании?
Quick sort выбирает pivot, разделяет массив на элементы меньше и больше pivot и рекурсивно сортирует части. В среднем это O(n log n), но при плохом pivot может быть O(n^2). В отличие от merge sort, quick sort часто реализуют in-place, но он не дает такой же гарантии worst-case без дополнительных приемов.
Что важно помнить: частые ошибки
- Говорить, что quick sort всегда
O(n log n). - Не учитывать worst case.
- Выбирать плохой pivot.
- Писать простую версию с массивами и называть ее
O(1)по памяти. - Не обрабатывать равные элементы.
Мини-шпаргалка
- Pivot - опорный элемент.
- Partition - главный шаг.
- Average
O(n log n). - Worst
O(n^2). - Memory зависит от реализации.
- Pivot strategy важна.