Алгоритмы

Quick Sort: Самый быстрый на практике

Цели урока

  • Понять partition и его роль
  • Реализовать Quick Sort с разными стратегиями pivot
  • Анализировать best/average/worst case
  • Сравнить с Merge Sort

Предварительные знания

  • Merge Sort
  • Рекурсия
  • Merge Sort

Тони Хоар придумал Quick Sort в 1960 году и назвал его 'Quicksort' потому что думал, что это самый быстрый алгоритм. 60 лет спустя это всё ещё самый используемый алгоритм сортировки в мире.

  • C qsort(), C++ std::sort (Introsort), Java Arrays.sort (для примитивов)
  • Базы данных - ORDER BY для небольших результатов
  • Встроенные системы - in-place, не нужна доп. память
  • Собеседования - классика

История Quick Sort

Тони Хоар изобрёл Quick Sort в 1960 году, работая над машинным переводом в МГУ. Он хотел отсортировать слова русского языка для словаря. Алгоритм был опубликован в 1961 году и остаётся одним из самых влиятельных в истории CS.

Идея: Partition вокруг pivot

**Quick Sort** - тоже Divide & Conquer, но с другим подходом:

  1. Выбираем **pivot** (опорный элемент)
  2. **Partition:** переставляем элементы так, чтобы меньшие pivot слева, большие справа
  3. Рекурсивно сортируем левую и правую части

**Ключевое отличие от Merge Sort:** работа делается ДО рекурсии (partition), а не ПОСЛЕ (merge). Это позволяет работать in-place!

После partition pivot находится:

Реализация Partition (Lomuto)

**Lomuto partition** - простая версия, pivot в конце массива:

**Hoare partition** - оригинальная версия, работает с двух концов. Быстрее Lomuto (~3x меньше swap), но сложнее.

Lomuto partition делает сколько swap-ов в худшем случае (все элементы < pivot)?

Полный Quick Sort

**Оптимизация:** tail recursion elimination для уменьшения глубины стека:

**Эта оптимизация** гарантирует глубину стека O(log n) даже в худшем случае. IntroSort (C++ std::sort) использует эту технику.

Quick Sort in-place - это значит:

Выбор pivot: искусство и наука

**Выбор pivot критически важен** - от него зависит, будет ли сортировка O(n log n) или O(n²).

СтратегияПлюсыМинусы
Первый/последнийПростотаO(n²) на отсортированных данных
СлучайныйИзбегает worst caseOverhead на random
Median-of-threeХороший баланс3 сравнения extra
Median-of-mediansO(n log n) гарантияСложный, большие константы

**Атака на Quick Sort:** если противник знает стратегию выбора pivot, он может подать данные, вызывающие O(n²). Randomized pivot защищает от этого.

Quick Sort с первым элементом как pivot на отсортированном массиве работает за:

Анализ сложности

СлучайСложностьКогда происходит
BestO(n log n)Pivot делит массив пополам
AverageO(n log n)Случайные данные
WorstO(n²)Pivot всегда min/max (отсортированные данные + плохой pivot)

**Space Complexity:** O(log n) в лучшем/среднем случае (глубина стека), O(n) в худшем. С оптимизацией tail recursion - O(log n) гарантированно.

Почему randomized Quick Sort имеет ожидаемое время O(n log n)?

Quick Sort vs Merge Sort

КритерийQuick SortMerge Sort
Worst caseO(n²)O(n log n)
AverageO(n log n)O(n log n)
SpaceO(log n)O(n)
In-placeДаНет
СтабильностьНетДа
Cache localityОтличнаяСредняя
Практическая скоростьБыстрееМедленнее

**Почему Quick Sort быстрее на практике?**

  1. **Cache locality** - работает с соседними элементами
  2. **In-place** - нет overhead на allocation
  3. **Меньше moves** - элементы перемещаются реже
  4. **Branch prediction** - предсказуемые условия

**IntroSort** (C++ std::sort) - гибрид: начинает как Quick Sort, переключается на Heap Sort при глубокой рекурсии. Так получаем скорость Quick Sort с гарантией O(n log n).

Когда выбрать Merge Sort вместо Quick Sort?

Quick Sort

  • Partition: делим на < pivot и > pivot
  • Pivot выбор критически важен
  • O(n log n) average, O(n²) worst (редко)
  • In-place, O(log n) стек
  • Быстрее Merge Sort на практике
  • Introsort = Quick + Heap для гарантии O(n log n)

Связанные темы

Quick Sort - основа многих оптимизированных алгоритмов.

  • Heap Sort — O(n log n) гарантия, используется в Introsort
  • Quick Select — K-й элемент за O(n)
  • 3-way Partition — Для данных с повторами

Вопросы для размышления

  • Quick Sort делит массив по pivot in-place. Worst case O(n²) возникает при плохом выборе pivot. В реальных задачах алгоритм ведёт себя почти идеально - при случайных данных. Задача: дан частично отсортированный массив (90% данных уже упорядочено). Какой pivot-стратегией и почему воспользоваться, чтобы избежать деградации к O(n²)?

Связанные уроки

  • alg-05-merge-sort — Merge Sort стабильный и гарантированный O(n log n), Quick Sort быстрее на практике из-за cache locality и in-place
  • alg-07-heap-sort — Heap Sort используется как fallback в Introsort именно потому, что Quick Sort может деградировать до O(n^2)
  • alg-19-divide-conquer — Quick Sort - Divide & Conquer, где разбиение выполняется ДО рекурсии, в отличие от Merge Sort
  • alg-08-counting-sort — 3-way partition Quick Sort (для данных с повторами) схож по идее с распределением по корзинам
  • prog-09-recursion — Tail recursion elimination в Quick Sort - важная оптимизация стека, требует понимания рекурсии
  • ds-01-arrays
Quick Sort: Самый быстрый на практике

0

1

Войти