Алгоритмическая сложность быстрой сортировки: теория и практика

Какая алгоритмическая сложность у "быстрой сортировки"?

Всегда O(n log n), независимо от входных данных.

Средняя временная сложность — O(n log n), худшая — O(n²).

Всегда O(n²), так как это нестабильный алгоритм.

В лучшем случае O(n), в худшем — O(n log n).

Теория: как работает quicksort

Quicksort — алгоритм «разделяй и властвуй»: выбирается опорный элемент (pivot), массив переставляется так, чтобы элементы меньше pivot оказались слева, а больше — справа, после чего обе части сортируются рекурсивно. Ключевое свойство: одна операция разбиения (partition) за один проход просматривает элементы подмассива, поэтому стоимость разбиения порядка O(n) для подмассива длины n.

Временная сложность определяется тем, насколько «ровно» pivot делит массив на две части. Если pivot каждый раз близок к медиане, дерево рекурсии имеет глубину порядка log n, и на каждом уровне суммарно обрабатывается около n элементов, что даёт O(n log n).

Разбор сложностей по случаям

Удобная модель анализа задаётся рекуррентным соотношением (для массива из n элементов): T(n) = T(k) + T(n - k - 1) + O(n) — где k это размер левой части после разбиения, а O(n) это стоимость partition.

Лучший (сбалансированный) случай
Если каждый раз k ≈ n/2, то получается: T(n) ≈ 2*T(n/2) + O(n) ⇒ T(n) = O(n log n) (стандартный результат для divide-and-conquer). Именно поэтому утверждение «в лучшем случае O(n)» не подходит для классического quicksort.
Средний / ожидаемый случай
Математический анализ показывает, что в среднем quicksort делает O(n log n) сравнений. Если pivot выбирается случайно (равновероятно из элементов подмассива), та же оценка ожидаемого времени применяется к любому входному массиву, а ожидание берётся по случайному выбору pivot.
Худший случай
Самое «косое» разбиение — когда одна часть имеет размер n-1, а другая 0, и это повторяется на каждом шаге; тогда суммарная работа становится квадратичной, O(n²). В учебных реализациях худший случай часто возникает на уже отсортированном массиве при выборе pivot как первого или последнего элемента.

Небольшая схема дерева рекурсии (идея):

Сбалансировано (≈ n/2 и n/2):          Несбалансировано (0 и n-1):
уровень 0:     n                         уровень 0:     n
уровень 1:  n/2  n/2                     уровень 1:     n-1
уровень 2: n/4 n/4 n/4 n/4               уровень 2:     n-2
...
глубина: ~log n                          глубина: ~n
работа/уровень: ~n                       суммарно: n+(n-1)+...+1 ≈ n²/2

На практике quicksort остаётся быстрым «в среднем», но без мер против худшего случая (удачный выбор pivot, гибридные подходы) возможны редкие, но очень медленные запуски на «неудачных» данных.

Пример кода (JS/TS) и комментарии

Ниже приведён простой учебный вариант quicksort (не in-place), чтобы увидеть идею разбиения; асимптотика по времени остаётся такой же, а по памяти появляется дополнительное выделение массивов.

// TypeScript / JavaScript (учебная реализация, не in-place)
export function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left: number[] = [];
  const right: number[] = [];
  const equal: number[] = [];

  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)];
}

Что важно заметить в этом коде:

Цикл for делает один линейный проход по arr, то есть разбиение стоит O(n) для текущего n.
Далее выполняются два рекурсивных вызова для частей массива, поэтому итог зависит от баланса размеров этих частей (сводится к формуле T(n) = T(k) + T(n-k-1) + O(n)).

Мини-таблица оценок (для «классического» quicksort по времени):

Случай	Временная сложность	Интуитивная причина
Лучший	`O(n log n)`	Почти равные разбиения на каждом шаге.
Средний	`O(n log n)`	В среднем число сравнений порядка `n log n`.
Худший	`O(n²)`	Постоянно получается разбиение `0` и `n-1`.

Нестабильность quicksort означает, что равные элементы могут поменять относительный порядок, но это не «превращает» алгоритм в O(n²) всегда; нестабильность — отдельная характеристика, не равная времени работы.

Итогоо: quicksort имеет среднюю (и ожидаемую при случайном выборе pivot) временную сложность O(n log n), но в худшем случае может деградировать до O(n²) из‑за крайне неравномерных разбиений; правильный вариант ответа — 2.