re:re:actable
Урок 054 минуты чтения

Что такое 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 важна.

Документация

Wikipedia: Quicksort.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам