Быстрая сортировка

Идея

Разделяй и властвуй, но основная работа делается до рекурсии:

1. Выбираем опорный элемент.
2. Разбиение: переставляем массив так, чтобы элементы не больше опорного оказались перед ним, а не меньше — после. Опорный элемент теперь на своём окончательном месте.
3. Рекурсивно сортируем обе части.

В отличие от сортировки слиянием, сливать ничего не нужно и дополнительный массив не используется.

Реализация следует Хоару и Седжвику:

• Медиана из трёх — опорным становится медиана первого, среднего и последнего элемента. На отсортированных и обратных массивах это настоящая медиана, и они становятся лучшим случаем вместо худшего.
• Разбиение Хоара — два индекса движутся навстречу друг другу и меняют местами элементы, стоящие не на своей стороне. Оба останавливаются на элементах, равных опорному, поэтому массивы с множеством повторов делятся поровну.
• Рекурсия в меньшую часть, цикл — для большей: стек вызовов никогда не растёт больше O(log n).

Пример

Сортируем [5, 2, 4, 6, 1, 3].

Опорный элемент. Первый, средний и последний — 5, 4, 3; их медиана 4 переносится в начало: 4, 2, 3, 6, 1, 5.

Разбиение вокруг 4 — i идёт вправо, пока элементы меньше 4, j идёт влево, пока элементы больше 4:

Шаг	Массив	Комментарий
начало	4, 2, 3, 6, 1, 5	опорный 4 на позиции 0
i остановился на 6, j — на 1	4, 2, 3, 6, 1, 5	оба не на своей стороне
обмен	4, 2, 3, 1, 6, 5
индексы пересеклись	4, 2, 3, 1, 6, 5	j = 3
опорный ↔ A[j]	1, 2, 3, 4, 6, 5	4 на своём месте

Рекурсия. [1, 2, 3] и [6, 5] сортируются так же: 1, 2, 3, 4, 5, 6.

Попробуйте сами

Тот же пример по шагам. Измените данные или нажмите «Старт».

Псевдокод

QUICK-SORT(A, low, high)
  while low < high
    p = PARTITION(A, low, high)
    if p − low < high − p              // рекурсия в меньшую часть
      QUICK-SORT(A, low, p − 1)
      low = p + 1
    else
      QUICK-SORT(A, p + 1, high)
      high = p − 1

PARTITION(A, low, high)                // Хоар, как у Седжвика
  move the median of A[low], A[mid], A[high] to A[low]
  pivot = A[low]
  i = low, j = high + 1
  loop
    repeat i = i + 1 while i < high and A[i] < pivot
    repeat j = j − 1 while pivot < A[j]
    if i ≥ j
      break
    swap A[i] and A[j]
  swap A[low] and A[j]
  return j

Сложность

Лучший	Средний	Худший	Память	Устойчивая	На месте
O(n log n)	O(n log n)	O(n²)	O(log n)	нет	да

• В среднем: если опорный элемент делит массив в разумной пропорции, глубина рекурсии O(log n), и на каждом уровне выполняется O(n) работы. На случайных данных со случайным опорным элементом делается около $1,39n{\log }_{2}n$ сравнений, с медианой из трёх — меньше.
• Худший случай O(n²) — когда опорный элемент всегда наименьший или наибольший. С опорным «последний элемент» это ровно отсортированный массив! Медиана из трёх исправляет отсортированные, обратные и одинаковые данные (тесты библиотеки проверяют ≤ 1,5 n log₂ n сравнений на них), но специально подобранные входные данные («убийцы медианы из трёх») всё ещё существуют. Кормен обходит проблему с высокой вероятностью, выбирая опорный элемент случайно.
• Память O(log n) на стек вызовов благодаря рекурсии в меньшую часть.
• Неустойчивая: разбиение меняет местами далёкие элементы.

Когда применять

На практике самая быстрая универсальная сортировка сравнением: мало перемещений данных и хорошая работа с кэшем. Если нужна устойчивость или гарантированные O(n log n), выбирайте слияние; introsort (быстрая сортировка, которая переключается на пирамидальную при слишком глубокой рекурсии) сочетает преимущества обеих.

Использование

import { quickSort } from 'ts-ds';

const words = ['груша', 'инжир', 'банан', 'киви'];
quickSort(words, (a, b) => a.length - b.length);

Справочник API

Литература

• C. A. R. Hoare. «Quicksort». The Computer Journal 5(1), 1962.
• Кормен, глава 7 «Быстрая сортировка» (разбиение Ломуто, рандомизированная версия, анализ).
• Седжвик, Алгоритмы, §2.3 «Быстрая сортировка» (разбиение Хоара, медиана из трёх).
• D. Musser. «Introspective Sorting and Selection Algorithms», 1997.