Второй кит O(n log n)
Quicksort — второй фундаментальный алгоритм сортировки. По асимптотике он такой же, как merge sort (O(n log n) в среднем), но в практической работе часто быстрее merge sort, потому что:
- in-place — не требует O(n) дополнительной памяти;
- cache-friendly — partition читает массив последовательно, лучше работает с CPU cache;
- простая константа — мало overhead, мало вспомогательных операций.
Но у него есть подвох: в худшем случае работает O(n^2). И этот worst case — не редкость на «плохих» данных. Поэтому реальные библиотеки не используют чистый quicksort — используют introsort (quicksort с fallback на heapsort при глубокой рекурсии) или Timsort (merge + insertion).
Несмотря на это, понимать quicksort обязательно — он лежит в основе многих современных алгоритмов и часто появляется на собеседованиях.
Идея
- Выбираем «опорный» элемент — pivot.
- Partition: переставляем массив так, чтобы все элементы меньше pivot были слева, все больше — справа.
- После partition pivot стоит на своём финальном месте.
- Рекурсивно сортируем левую и правую части.
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)Lomuto partition
Самый простой вариант partition: pivot = arr[hi] (последний элемент).
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1Идея:
iотслеживает «границу» меньших-равных pivot.jидёт по всему диапазону.- Если
arr[j] <= pivot, инкрементим i и меняем arr[i] и arr[j]. - В конце меняем arr[i+1] с pivot — pivot оказывается на месте.
Пример: [3, 6, 8, 2, 7, 4, 1, 5], pivot=5.
- j=0: 3 ≤ 5, i=0, swap(0,0):
[3, 6, 8, 2, 7, 4, 1, 5]. - j=1:
6 > 5, пропуск. - j=2:
8 > 5. - j=3: 2 ≤ 5, i=1, swap(1,3):
[3, 2, 8, 6, 7, 4, 1, 5]. - j=4:
7 > 5. - j=5: 4 ≤ 5, i=2, swap(2,5):
[3, 2, 4, 6, 7, 8, 1, 5]. - j=6: 1 ≤ 5, i=3, swap(3,6):
[3, 2, 4, 1, 7, 8, 6, 5]. - Финальный swap(4, hi):
[3, 2, 4, 1, 5, 8, 6, 7]. Pivot=5 на месте 4.
После partition: левая часть [3, 2, 4, 1], правая [8, 6, 7]. Сортируем рекурсивно.
Pivot = последний элемент. Указатели i и j двигаются.
Hoare partition
Альтернатива — Hoare partition (исторически первая). Указатели идут навстречу друг другу.
def hoare_partition(arr, lo, hi):
pivot = arr[(lo + hi) // 2]
i = lo - 1
j = hi + 1
while True:
i += 1
while arr[i] < pivot:
i += 1
j -= 1
while arr[j] > pivot:
j -= 1
if i >= j:
return j
arr[i], arr[j] = arr[j], arr[i]
def quicksort_hoare(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = hoare_partition(arr, lo, hi)
quicksort_hoare(arr, lo, p)
quicksort_hoare(arr, p + 1, hi)Hoare:
- В среднем делает меньше swap’ов, чем Lomuto.
- Сложнее в реализации, легче ошибиться с границами.
- Pivot не оказывается на финальной позиции; возвращается не индекс pivot, а индекс конца левой части.
В современных libs (например, в std::sort C++) обычно используют Hoare-like подходы.
Сложность
O(n log n) в среднем, O(n^2) в худшем случае.
Когда O(n^2) — реально
С pivot = последний элемент (Lomuto) на уже отсортированном массиве quicksort деградирует. Каждый partition разделяет массив на n-1 и 0 элементов. Дерево рекурсии — цепочка длиной n. Работа на каждом уровне — O(n). Итого O(n^2).
import time
def quicksort_naive(arr, lo=0, hi=None):
# та же реализация Lomuto, что выше
...
# уже отсортированный массив
arr_sorted = list(range(10000))
t = time.perf_counter()
quicksort_naive(arr_sorted[:])
print(time.perf_counter() - t)
# ~2-5 секунд — это O(n^2)10 000 элементов и 5 секунд — катастрофа. На случайном массиве той же длины — миллисекунды.
Защита: random shuffle и random pivot
Решений два:
1. Random shuffle перед quicksort
Перед запуском перемешиваем массив:
import random
def quicksort_safe(arr):
random.shuffle(arr) # O(n), гарантирует random order
quicksort(arr)После shuffle вероятность patological-сlucha -> 0. Average O(n log n) с очень высокой вероятностью.
2. Random pivot
Внутри partition выбираем pivot случайно, а не arr[hi]:
import random
def partition_random(arr, lo, hi):
rand_idx = random.randint(lo, hi)
arr[rand_idx], arr[hi] = arr[hi], arr[rand_idx] # перенесли в позицию hi
# дальше обычный Lomuto
...Это даёт ту же гарантию: даже на отсортированном массиве quicksort работает O(n log n) в среднем.
3. Median-of-three
Третий приём: pivot = медиана из {arr[lo], arr[mid], arr[hi]}. Гарантирует, что на отсортированном массиве не возьмём крайний элемент. На большинстве реальных данных работает.
Современные libs используют комбинацию: median-of-three (или median-of-medians) + переключение на heapsort при глубокой рекурсии (introsort).
Зачем quicksort, если есть Timsort
Timsort быстрее на реальных данных (адаптивный). Но quicksort:
- In-place — критично для embedded и для огромных массивов в RAM.
- Меньше allocations — Timsort требует O(n) temp buffer; quicksort — только stack.
- Простая реализация — quicksort короче Timsort.
- Standard в C++/Rust — std::sort обычно introsort.
В Python для пользовательского кода всегда sorted(). Знание quicksort нужно для интервью и для понимания std::sort, std::partition, std::nth_element в C++.
Quickselect: топ-k без полной сортировки
Quicksort partition имеет другое применение: quickselect. Найти k-й по величине элемент без полной сортировки.
def quickselect(arr, k):
"""Возвращает k-th smallest element. O(n) в среднем."""
if len(arr) == 1:
return arr[0]
pivot = arr[len(arr) // 2]
lows = [x for x in arr if x < pivot]
highs = [x for x in arr if x > pivot]
pivots = [x for x in arr if x == pivot]
if k < len(lows):
return quickselect(lows, k)
elif k < len(lows) + len(pivots):
return pivot
else:
return quickselect(highs, k - len(lows) - len(pivots))Это O(n) в среднем — мы рекурсивно идём только в одну часть. Worst case O(n^2), но с median-of-medians можно гарантировать O(n).
В Python есть heapq.nlargest(k, arr) и heapq.nsmallest(k, arr) — это O(n log k), не O(n), но более стабильно и без рекурсии.
DE-кейс: топ-100 пользователей по revenue
Сценарий: миллион пользователей, нужно вывести 100 с наибольшим revenue. Sort всей таблицы — O(n log n) = ~20М операций.
Через quickselect-like — O(n + k log k) = ~1М + 600 = ~1М операций. В 20 раз быстрее.
В Python это heapq.nlargest(100, users, key=lambda u: u.revenue) — внутри O(n log k).
В Spark/SQL: ORDER BY revenue DESC LIMIT 100. Хороший движок применяет top-k оптимизацию (priority queue), не full sort.
Попробуй сам
import random
import time
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
pivot = arr[hi]
i = lo - 1
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1]
return i + 1
# тест на случайных
random.seed(0)
arr_random = [random.randint(0, 10**6) for _ in range(10_000)]
arr_sorted = sorted(arr_random)
arr_reverse = arr_sorted[::-1]
for name, arr in [("random", arr_random), ("sorted", arr_sorted), ("reverse", arr_reverse)]:
a = arr[:]
t = time.perf_counter()
try:
quicksort(a)
elapsed = time.perf_counter() - t
print(f"{name}: {elapsed*1000:.1f} ms")
except RecursionError:
print(f"{name}: RecursionError (too deep)")Ожидаемое:
- random: 10-30 мс,
- sorted: RecursionError или 2-5 секунд (O(n^2) + stack overflow),
- reverse: то же самое.
Теперь повторите с защитой:
import random
random.shuffle(arr_sorted) # уже не отсортирован
quicksort(arr_sorted) # сработает за O(n log n)В следующем уроке — почему quicksort часто быстрее merge sort на одних и тех же данных, несмотря на одинаковую асимптотику. Виноваты cache и in-place.