DEV//UNIT
← АлгоритмыSorting

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

Разбиение вокруг опорного: меньшие влево, большие вправо — и рекурсия в обе половины.

время O(n log n) в среднемпамять O(log n)уровень: начальный
Что происходит сейчас0/0
Нажмите Play, чтобы запустить сценарий
TypeScript — активная строка подсвечена шагом
1function quickSort(a: number[], lo = 0, hi = a.length - 1): number[] {
2  if (lo >= hi) return a
3 
4  const p = partition(a, lo, hi)
5  quickSort(a, lo, p - 1)
6  quickSort(a, p + 1, hi)
7  return a
8}
9 
10function partition(a: number[], lo: number, hi: number): number {
11  const pivot = a[hi]
12  let i = lo - 1
13 
14  for (let j = lo; j < hi; j++) {
15    if (a[j] < pivot) {
16      i++
17      swap(a, i, j)
18    }
19  }
20  swap(a, i + 1, hi)
21  return i + 1
22}

Проблема

Отсортировать быстро в среднем и без лишней памяти. Наивная идея «разделяй и властвуй»: выбрать опорный элемент, разделить массив относительно него, повторить в частях.

Что вы видите

Столбики: опорный подсвечен фиолетовым, j сканирует зону сверху, i снизу держит границу «меньших». Элементы меньше опорного прыгают за i; в конце опорный встаёт на своё место навсегда.

Как это работает

Lomuto-схема: после прохода j все элементы меньше опорного собраны в префиксе, опорный обменивается с его границей — позиция опорного окончательна. Рекурсия в левую и правую части. В среднем O(n log n) с малой константой; худший случай O(n²) лечится случайным выбором опорного.

Пошаговый разбор

  1. 01

    Опорный

    Последний элемент зоны.

  2. 02

    Сканирование

    j идёт по зоне, сравнивая с опорным.

  3. 03

    Меньшие влево

    a[j] < опорный → обмен за границу i.

  4. 04

    Опорный на место

    Обмен с i+1 — позиция окончательна.

  5. 05

    Рекурсия

    То же слева и справа.

Complexity и ограничения

time
O(n log n) в среднем
space
O(log n)

В среднем O(n log n), на практике быстрее Merge из-за кэша. Худший случай O(n²) при неудачных опорных. Неустойчива.

Edge cases

  • Уже отсортирован + крайний опорный

    Худший случай — лечится случайным опорным.

  • Все равные

    Lomuto деградирует;三点ная разбиение (Dutch flag) решает.

  • Малые зоны

    Вставки внутри — гибрид Introsort (C++ std::sort).

Где встречается в реальности

Стандартные библиотеки

C++ introsort, Rust pattern-defeating quicksort — семейство quick.

Базы данных

Внутренние сортировки узлов — как правило, quick-гибриды.

Выбор k-го по величине

Quickselect — разбиение без полной рекурсии.

Связанные алгоритмы

Сортировка выборомСортировка слиянием
Shorts

«Почему самая быстрая сортировка — «разделить и властвовать»»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Почему самая быстрая сортировка — «разделить и властвовать»
Нажмите Play
Бит 1/6 · 0–2 с
Hook
script-setup.ru/algorithms/quick-sort