Разбираемся с быстрой сортировкой на примерах JavaScript

Быстрая сортировка (quicksort) — это алгоритм сортировки, работающий по принципу «разделяй и властвуй»: он выбирает опорный элемент (pivot), разбивает массив так, чтобы меньшие элементы оказались слева, а большие — справа, а затем рекурсивно сортирует каждую часть на месте.

Большинство из нас впервые сталкивается с ним у доски под чьим-то пристальным взглядом, и именно на цикле разбиения уверенность обычно улетучивается. Алгоритм работает за O(n log n) в среднем случае, сортирует без выделения второго массива и чаще всего именно его выбирают интервьюеры, когда просят «отсортировать это вручную».

В этой статье разберём три вещи: наглядную версию для формирования интуитивного понимания, пошаговый разбор одного прохода разбиения, чтобы вы увидели, как перемещаются элементы, и реализацию на месте (in-place), которую вы действительно написали бы на собеседовании, а также заметки о сложности, выборе опорного элемента и стабильности.

Как работает алгоритм быстрой сортировки?

Быстрая сортировка сортирует массив, многократно разделяя его вокруг выбранного опорного элемента. Один проход разбиения переставляет элементы так, чтобы всё, что меньше опорного элемента, оказалось перед ним, а всё, что больше, — после него; после этого опорный элемент находится на своей окончательной позиции. Примените тот же шаг к левому и правому поддиапазонам — и весь массив отсортируется сам собой.

Алгоритм имеет ту же структуру «разделяй и властвуй», что и сортировка слиянием, но компромиссы у них разные. И быстрая сортировка, и сортировка слиянием в среднем дают O(n log n), но быстрая сортировка работает на месте с O(log n) вспомогательной памяти, тогда как сортировке слиянием нужно O(n) дополнительной памяти; при этом сортировка слиянием стабильна, а быстрая — нет. Быстрая сортировка обменивает гарантированную стабильность на меньший расход памяти и высокую реальную скорость.

Сначала наглядная версия (filter и spread)

Самая простая для чтения версия быстрой сортировки выполняет разбиение с помощью filter и собирает массив заново через spread-оператор. Это самый быстрый способ понять рекурсию и отличный учебный инструмент, но при каждом вызове выделяются новые массивы, поэтому такая версия не работает на месте и потребляет дополнительную память.

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  const [pivot, ...rest] = arr;
  const left = rest.filter((x) => x < pivot);
  const right = rest.filter((x) => x >= pivot);

  return [...quickSort(left), pivot, ...quickSort(right)];
}

quickSort([3, 7, 2, 5, 1, 4, 6, 8]); // [1, 2, 3, 4, 5, 6, 7, 8]

Базовый случай (length <= 1) останавливает рекурсию, поскольку массив из нуля или одного элемента уже отсортирован. Каждый вызов создаёт три новых массива, поэтому потребление памяти в этой версии растёт вместе с размером входных данных, а не остаётся постоянным. Используйте её, чтобы объяснить идею; для случаев, когда важна память или ожидания на собеседовании, обращайтесь к in-place-версии ниже.

Как работает разбиение?

Разбиение — это движок быстрой сортировки, поэтому стоит внимательно рассмотреть один проход. Схема Ломуто берёт последний элемент в качестве опорного, проходит по диапазону сканирующим индексом j и поддерживает граничный индекс i, отмечающий место, куда должен попасть следующий элемент «меньше опорного». Каждый раз, когда arr[j] меньше опорного элемента, происходит обмен arr[i] и arr[j], а i увеличивается. В конце опорный элемент меняется местами с позицией i.

Проследим за [7, 2, 1, 8, 6, 3, 5, 4] с опорным элементом 4 (последний элемент), начиная с i = 0:

Опорный элемент 4 встаёт на индекс 3, слева от него [2,1,3], справа — [6,7,5,8]. Ни одна из сторон ещё не отсортирована, но опорный элемент занял своё окончательное место, и обе стороны стали независимыми подзадачами.

function partition(arr, lo, hi) {
  const pivot = arr[hi];          // last element as pivot
  let i = lo;                     // boundary for elements < pivot
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      [arr[i], arr[j]] = [arr[j], arr[i]];
      i++;
    }
  }
  [arr[i], arr[hi]] = [arr[hi], arr[i]]; // move pivot into place
  return i;
}

Быстрая сортировка на месте, которую вы написали бы на собеседовании

Приближённая к продакшену версия быстрой сортировки использует показанную выше вспомогательную функцию разбиения и рекурсивно обрабатывает диапазоны индексов (lo, hi) вместо создания новых массивов. Именно эту версию стоит использовать, когда вас просят реализовать quicksort: она изменяет один массив и расходует дополнительную память только на стек рекурсии.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo < hi) {
    const p = partition(arr, lo, hi);
    quickSort(arr, lo, p - 1);
    quickSort(arr, p + 1, hi);
  }
  return arr;
}

quickSort([7, 2, 1, 8, 6, 3, 5, 4]); // [1, 2, 3, 4, 5, 6, 7, 8]

Каждый вызов разбивает свой диапазон, а затем рекурсивно обрабатывает два поддиапазона по обе стороны от опорного элемента. Проверка lo < hi — это базовый случай: диапазон из нуля или одного элемента уже отсортирован. Если рекурсия недопустима (частый уточняющий вопрос на собеседовании), та же логика преобразуется в итеративную версию: пары lo/hi складываются в явный стек вместо стека вызовов.

Сложность, выбор опорного элемента и стабильность

Стоимость быстрой сортировки почти полностью определяется опорным элементом. При сбалансированных разбиениях каждый уровень рекурсии затрагивает каждый элемент один раз примерно на log n уровнях, что даёт O(n log n). Когда разбиения стабильно несбалансированы, глубина рекурсии вырастает до n, а стоимость деградирует до O(n²). При реализации на месте стек рекурсии занимает O(log n) памяти на сбалансированных входных данных.

Классическая ловушка: выбор первого или последнего элемента в качестве опорного приводит к худшему случаю O(n²) на уже отсортированных данных, поскольку каждое разбиение отсекает всего один элемент. Избежать худшего случая на отсортированных данных можно, выбирая средний элемент, применяя метод «медиана из трёх» или выбирая случайный опорный элемент. Метод «медиана из трёх» упорядочивает первый, средний и последний элементы и использует медиану, что устойчиво как к отсортированным, так и к обратно отсортированным «злонамеренным» входным данным:

function medianOfThree(arr, lo, hi) {
  const mid = Math.floor((lo + hi) / 2);
  if (arr[mid] < arr[lo]) [arr[lo], arr[mid]] = [arr[mid], arr[lo]];
  if (arr[hi]  < arr[lo]) [arr[lo], arr[hi]]  = [arr[hi], arr[lo]];
  if (arr[hi]  < arr[mid]) [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  // median now sits at mid; move it to hi so Lomuto uses it as the pivot
  [arr[mid], arr[hi]] = [arr[hi], arr[mid]];
  return arr[hi];
}

Одно свойство не вернёт никакая стратегия выбора опорного элемента: быстрая сортировка не является стабильной, поэтому равные элементы могут поменять взаимный порядок относительно исходных позиций. Это важно, когда вы сортируете записи по вторичному ключу и рассчитываете, что первичный порядок сохранится.

Использует ли встроенная сортировка JavaScript алгоритм quicksort?

Нет. Хотя алгоритм быстрой сортировки нестабилен, встроенный в JavaScript метод Array.prototype.sort гарантированно стабилен начиная с ES2019, десятой редакции стандарта языка. V8 сортирует массивы с помощью Timsort начиная с версии 7.0 и Chrome 70: это сортировка слиянием, которая использует уже упорядоченные участки данных и сохраняет исходный порядок равных элементов. Все остальные крупные движки обязаны соблюдать то же требование стабильности согласно спецификации. Так что фраза «быстрая сортировка нестабильна» описывает алгоритм, а не встроенный sort в любом современном браузере.

Быстрая сортировка заслужила свою репутацию благодаря компактному циклу разбиения, работе на месте и средней скорости O(n log n) — при условии, что вы не берёте опорный элемент с краёв массива. Реализуйте приведённую выше in-place-версию с медианой из трёх или случайным опорным элементом, прогоните её на отсортированных данных, чтобы убедиться, что она не «взрывается», — и вы сможете как написать quicksort, так и объяснить его компромиссы по первому требованию.

Часто задаваемые вопросы

Когда стоит использовать быструю сортировку вместо сортировки слиянием?

Используйте быструю сортировку, когда память ограничена и нужно сортировать на месте, поскольку ей требуется лишь O(log n) вспомогательной памяти под стек рекурсии против O(n) дополнительного массива у сортировки слиянием. Обе в среднем дают O(n log n), но быстрая сортировка на практике работает быстрее на типичных данных. Выбирайте сортировку слиянием, когда нужна гарантированная стабильность или гарантированный худший случай O(n log n), поскольку быстрая сортировка может деградировать до O(n в квадрате).

Почему быстрая сортировка деградирует до O(n в квадрате) на уже отсортированном массиве?

Фиксированный опорный элемент (первый или последний) деградирует до O(n в квадрате) на отсортированных данных, потому что каждое разбиение помещает опорный элемент на край и порождает один пустой поддиапазон и один диапазон из n минус 1 элементов. Это даёт n уровней рекурсии вместо log n, причём на каждом выполняется линейная работа. Решение — выбирать средний элемент, применять медиану из трёх или брать случайный опорный элемент; все эти подходы восстанавливают сбалансированные разбиения на отсортированных данных.

Реализован ли Array.prototype.sort в JavaScript через быструю сортировку?

Нет. Современные движки не используют quicksort для встроенной сортировки. V8 применяет Timsort начиная с версии 7.0 и Chrome 70 — это сортировка слиянием, использующая уже упорядоченные участки данных и сохраняющая порядок равных элементов. Начиная с ES2019 спецификация ECMAScript требует, чтобы Array.prototype.sort был стабильным, и все крупные движки поставляют стабильную сортировку. Таким образом, сам алгоритм quicksort нестабилен, но встроенная сортировка — это не quicksort, и её стабильность гарантирована.

В чём разница между схемами разбиения Ломуто и Хоара?

Схема Ломуто использует один сканирующий индекс и обычно берёт в качестве опорного последний элемент, перемещая меньшие элементы к граничному индексу; её проще писать и отслеживать. Схема Хоара использует два указателя, движущихся навстречу друг другу от обоих концов, и, как правило, выполняет меньше обменов, что делает её быстрее на практике. Обе выполняют разбиение на месте и возвращают точку раздела, но возвращаемый схемой Хоара индекс не ставит опорный элемент на его окончательную позицию, в отличие от схемы Ломуто.

Как преобразовать рекурсивную быструю сортировку в итеративную версию?

Замените стек вызовов явным стеком диапазонов индексов. Поместите в него начальную пару lo и hi, затем выполняйте цикл, пока стек не пуст: извлеките диапазон, разбейте его, получив индекс опорного элемента p, и поместите обратно в стек два поддиапазона — от lo до p минус 1 и от p плюс 1 до hi — если они содержат больше одного элемента. Это даёт тот же результат без рекурсии, что часто спрашивают на собеседованиях в качестве уточняющего вопроса.