Алгоритмы с нуля
Быстрая сортировка
Ты знаешь сортировку слиянием: раздели, сортируй каждую половину, объедини. Она всегда O(n log n), но требует O(n) дополнительной памяти. Быстрая сортировка иначе. Она выбирает элемент-стержень (pivot), переставляет массив так, чтобы всё меньше стержня было слева и всё больше было справа, потом рекурсивно сортирует левую и правую части. Её сила в скорости на практике: сортирует на месте (без нового массива), кэш-дружелюбна и в среднем O(n log n). Подвох: если стержень выбран плохо, может быть O(n²). Реальные языки используют быструю сортировку (или её варианты) потому что среднее быстро и память экономится.
После этого урока ты разбираешься в быстрой сортировке: как работает шаг partition (выберешь стержень, переставишь так чтобы меньше слева и больше справа, стержень попадает в финальную позицию), почему рекурсивный partition даёт O(n log n) в среднем (сбалансированный partition даёт log n уровней, каждый уровень O(n) работы), почему может быть O(n²) в худшем (несбалансированные partition когда стержень всегда минимум или максимум), как избежать худшего (случайный стержень или median-of-three), почему быстрая сортировка на месте и не стабильна, и как она сравнивается с сортировкой слиянием (быстрее на практике но не стабильна; слияние стабильно но требует лишнюю память).
Шаг partition: сердце быстрой сортировки
Быстрая сортировка начинается с ключевого перепада (partition): если ты сможешь переставить массив так чтобы выбранный элемент-стержень (pivot) оказался на финальной позиции, всё меньше его было слева, а всё больше справа, то задача раскололась на два независимых подзадачи. Сортируешь левую и правую части — готово.
Эта переставка называется partition. Выбираешь элемент как стержень (часто последний), потом проходишь массив и меняешь местами элементы так чтобы:
- Все элементы < стержня были слева.
- Стержень был на финальной позиции.
- Все элементы > стержня были справа.
После partition, стержень встал на место где быть в финальном отсортированном массиве. Больше он не пошевелится.
Partition в действии
Представь массив [3, 7, 2, 9, 1] со стержнем = 1 (последний элемент).
Хотим переставить так чтобы всё меньше 1 влево, 1 в центр, всё больше вправо. Но меньше 1 нет, поэтому результат partition [1, 7, 2, 9, 3] со стержнем на индексе 0. Теперь рекурсивно сортируем правую часть [7, 2, 9, 3].
Или [3, 7, 2, 9, 5] со стержнем = 5. Будем использовать Lomuto’s scheme — проще.
Scheme Lomuto для partition
Проще: поддерживаем границу между “меньше” и “больше” регионами. Проходим массив один раз. Если элемент меньше стержня, перемещаем его к границе (меняем с первым элементом в “больше” регионе) и сдвигаем границу.
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1; // финальная позиция стержня
}Проходим [3, 7, 2, 9, 1], стержень = 1:
j=0: arr[0]=3. 3 < 1? Нет. Пропускаем.j=1: arr[1]=7. 7 < 1? Нет. Пропускаем.j=2: arr[2]=2. 2 < 1? Нет. Пропускаем.j=3: arr[3]=9. 9 < 1? Нет. Пропускаем.- После цикла: меняем arr[i+1] (arr[0]=3) с arr[high] (arr[4]=1). Результат:
[1, 7, 2, 9, 3].
Стержень 1 теперь на индексе 0. Всё справа (индексы 1–4) больше. Рекурсивно сортируем [7, 2, 9, 3] (индексы 1–4) и [] (перед 0).
Почему O(n log n) в среднем?
В среднем, стержень раздели́т массив примерно пополам. То есть partition делает O(n) работы (один проход), потом рекурсивно сортируешь две половинки примерно одинакового размера. Это даёт:
- Уровень 1: O(n) partition на полном массиве.
- Уровень 2: O(n) partition на двух половинах.
- Уровень 3: O(n) partition на четырёх четвертинах.
- …
- Уровень log n: много малых partition, всё ещё O(n) в сумме.
Итого: log n уровней × O(n) работы = O(n log n).
Худший случай: O(n²)
Если стержень всегда минимум или максимум, partition становится несбалансированным. Левая часть пуста, правая размер n-1. Тогда:
- Уровень 1: O(n) partition, левая один элемент, правая n-1.
- Уровень 2: O(n-1) partition на правой.
- Уровень 3: O(n-2) partition на правой.
- …
- Уровень n: O(1).
Итого: n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n²).
Это происходит когда массив уже отсортирован (или обратно отсортирован) и выбираешь первый или последний элемент как стержень. Реальная проблема.
Как избежать худшего: выбери стержень поумнее
- Случайный стержень: Выбери случайный элемент. Вероятность попасть в худшее повторно экспоненциально мала.
- Median-of-three: Раздели на медиане из первого, среднего и последнего элементов. Снижает шанс плохого стержня.
- Introselect: Используй быструю сортировку, но если глубина рекурсии превышает 2 × log n, переключись на heap sort для гарантии O(n log n).
Большинство языков используют один из этих стратегий.
На месте и не стабильна
Быстрая сортировка переставляет массив без выделения нового массива. Память только стек вызовов: O(log n) в среднем (глубина рекурсии), O(n) в худшем.
Быстрая сортировка не стабильна: равные элементы могут переставиться. Если сортируешь объекты по ключу и равные значения должны сохранить порядок, быстрая сортировка его не сохранит (в отличие сортировки слиянием).
Быстрая сортировка vs сортировка слиянием
| Аспект | Быстрая сортировка | Сортировка слиянием |
|---|---|---|
| Время (среднее) | O(n log n) | O(n log n) |
| Время (худшее) | O(n²) | O(n log n) |
| Память | O(log n) среднее, O(n) худшее | O(n) |
| На месте? | Да | Нет |
| Стабильна? | Нет | Да |
| Кэш-дружелюбна? | Да | Нет (случайный доступ) |
Быстрая сортировка быстрее на практике на случайных данных потому что кэш-дружелюбна и на месте. Сортировка слиянием предсказуема и стабильна. Выбирай по потребностям.
Кодируем быструю сортировку с нуля.
Шаг 1: Функция partition (Lomuto scheme)
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}Функция берёт подмассив с индекса low по high, использует arr[high] как стержень, и переставляет подмассив так чтобы элементы меньше стержня были слева, больше справа. Возвращает финальную позицию стержня.
Шаг 2: Быстрая сортировка рекурсивно
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}Раздели́т массив, потом рекурсивно сортируй левую часть (индексы low по pi - 1) и правую часть (индексы pi + 1 по high). Когда low >= high, подмассив имеет 0 или 1 элементов и уже отсортирован.
Полный пример
function partition(arr, low, high) {
const pivot = arr[high];
let i = low - 1;
for (let j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
[arr[i], arr[j]] = [arr[j], arr[i]];
}
}
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
return i + 1;
}
function quickSort(arr, low = 0, high = arr.length - 1) {
if (low < high) {
const pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
const unsorted = [38, 27, 43, 3, 9, 82, 10];
quickSort(unsorted);
console.log("Отсортирован:", unsorted);Запустим:
Трассируем partition на массиве [3, 7, 2, 9, 1] со стержнем = 1 (arr[4]).
1
function partition(arr, low, high) {
2
const pivot = arr[high];
3
let i = low - 1;
4
for (let j = low; j < high; j++) {
5
if (arr[j] < pivot) {
6
i++;
7
[arr[i], arr[j]] = [arr[j], arr[i]];
8
}
9
}
10
[arr[i + 1], arr[high]] = [arr[high], arr[i + 1]];
11
return i + 1;
12
}
Этот partition поместил 1 (самый маленький) на индекс 0. Левая часть (перед 0) пуста, правая часть (индексы 1–4) содержит [7, 2, 9, 3] и больше стержня. Теперь рекурсивно быстро-сортируем правую часть.
| Аспект | Значение |
|---|---|
| Время (лучший случай) | O(n log n) |
| Время (средний случай) | O(n log n) |
| Время (худший случай) | O(n²) |
| Память (стек вызовов) | O(log n) среднее, O(n) худшее |
| Стабильна? | Нет |
| На месте? | Да |
Средний случай: O(n log n)
На случайных данных, стержень раздели́т массив примерно пополам. Это создаёт log n уровней partition, каждый делает O(n) работы, даёт O(n log n).
Худший случай: O(n²)
Если стержень всегда минимум или максимум, partition максимально несбалансирован. Только один элемент помещается правильно за шаг partition, создаёт n уровней partition, каждый делает O(n), O(n-1), O(n-2), … = O(n²).
Это происходит когда массив уже отсортирован и выбираешь первый или последний элемент. Но на случайных данных или с хорошей стратегией (случайный, median-of-three), это маловероятно.
Память
Быстрая сортировка использует O(log n) память в среднем (глубина рекурсии) и O(n) в худшем. Никакой временный массив не выделяется.
Стабильность
Быстрая сортировка не стабильна. Равные элементы могут переставиться при partition. Если нужна стабильность, используй сортировку слиянием или стабильный вариант быстрой сортировки (что копирует в временный массив, теряя преимущество памяти).
Что делает partition?
Когда быстрая сортировка O(n²) в худшем?
Как быстрая сортировка сравнивается с сортировкой слиянием по памяти?
Стабильна ли быстрая сортировка?
Если массив из 8 элементов раздели́т на левую размер 1 и правую размер 6 (несбалансированно), на сколько больше уровней partition чем сбалансированный (4 и 4)?
Частая ошибка
Быстрая сортировка катастрофа: отсортированный массив с наивным стержнем. У тебя отсортированный массив [1, 2, 3, 4, 5, 6, 7, 8] и используешь быструю сортировку со стержнем = arr[0]. Partition выбирает 1, движет на индекс 0 (уже там), правая часть это [2, 3, 4, 5, 6, 7, 8] (размер 7). Потом partition [2, 3, 4, 5, 6, 7, 8] со стержнем = 2. Выбирает 2, движет на индекс 0 этого подмассива, правая это [3, 4, 5, 6, 7, 8] (размер 6). Этот паттерн повторяется: n, n-1, n-2, …, 1 partition, каждый делает O(n) работы. Итого: O(n²). Поэтому реальные реализации используют лучшую стратегию — случайный или median-of-three.
Граничные случаи
Быстрая сортировка на дубликатах. Рассмотри [3, 1, 3, 2, 3]. С быстрой сортировкой (Lomuto partition), стержень 3 может оказаться где угодно среди дубликатов. Последующие partition переставят три тройки друг относительно друга. Поэтому быстрая сортировка не стабильна. Если нужна стабильность, используй сортировку слиянием или вариант что группирует равные элементы перед рекурсией.
Проектируешь реал-тайм систему что должна сортировать ID пользователей. Скорость главное, памяти мало. Вход случайный (не отсортирован или почти отсортирован). Выбираешь быструю сортировку или сортировку слиянием?
Быстрая сортировка выбирает стержень, раздели́т массив так чтобы стержень на финальной позиции, потом рекурсивно сортирует левую и правую части.
Partition переставляет массив: проходишь через, меняешь элементы так чтобы меньше были слева стержня и больше справа. Стержень попадает на финальную отсортированную позицию.
Время: O(n log n) в среднем (сбалансированные partition дают log n уровней, каждый O(n) работы). O(n²) худший если стержень всегда минимум или максимум (происходит на отсортированном вводе с наивным выбором).
Память: O(log n) среднее (глубина рекурсии), O(n) худшее. Никакой доп.массив.
На месте: Да. Массив переставляется без выделения нового.
Стабильна: Нет. Равные элементы могут переставиться при partition.
vs Сортировка слиянием: Быстрая быстрее на практике (кэш-дружелюбна, меньше памяти), но слияние стабильна и гарантирует O(n log n). Выбирай исходя из того нужна ли стабильность или гарантированный худший случай.
Почему учить? Быстрая сортировка дефолт в большинстве языков потому что быстра на практике. Понимание как работает partition учит тебя перестановке на месте и почему выбор стержня критичен для производительности.