Быстрая сортировка и разделение массива

Сортировка слиянием делит массив пополам по номерам и склеивает половины в конце. Быстрая сортировка делает наоборот: делит по значениям, а склеивать потом ничего не надо.

Идея

Выберем в массиве какое-нибудь значение $x$ — назовём его опорным. Переставим элементы так, чтобы слева оказались все, кто не больше $x$, а справа — все, кто не меньше.

Теперь отсортируем каждую половину по отдельности. Массив после этого будет отсортирован целиком: внутри половин порядок наведён, а любой элемент левой половины не больше любого элемента правой.

// Полуинтервал [l, r).
void quick_sort(vector<int>& a, int l, int r) {
    if (r - l <= 1) return;
    int k = partition(a, l, r);   // вернёт границу между половинами
    quick_sort(a, l, k);
    quick_sort(a, k, r);
}

Заметьте: массив передаётся по ссылке. Забыть амперсанд — классическая ошибка: тогда функция получит копию, отсортирует её и выбросит, а вызывающий код не увидит ничего. Копирование при этом будет происходить на каждом уровне рекурсии.

Разделение

Разделить можно наивно: завести два вектора, разложить элементы по ним и переписать обратно. Работает, но требует дополнительной памяти и времени на её выделение.

Лучше сделать это на месте, двумя указателями с концов.

Пусть $x$ — значение случайного элемента. Двигаем левый указатель вправо, пока он смотрит на элемент, меньший $x$. Двигаем правый указатель влево, пока он смотрит на элемент, больший $x$. Оба остановятся на «нарушителях» — элементах, стоящих не в своей половине. Меняем их местами и продолжаем.

int partition(vector<int>& a, int l, int r) {
    int x = a[l + rand() % (r - l)];
    int L = l, R = r - 1;
    while (true) {
        while (a[L] < x) ++L;
        while (a[R] > x) --R;
        if (L >= R) break;
        swap(a[L], a[R]);
        ++L;
        --R;
    }
    return R + 1;
}

Зачем нужен выход по L ≥ R

Может случиться, что нарушителя с одной стороны нет. Например, левый указатель встал на элемент, больший $x$, а правый, двигаясь навстречу, прошёл мимо него и оказался левее. Это значит, что весь массив уже разделён и менять нечего — как раз этот случай и ловит break.

Строгие сравнения в обоих циклах (< и >, а не <= и >=) выбраны намеренно. С нестрогими указатель проскакивает мимо элементов, равных опорному, и на массиве из одинаковых чисел уезжает за границу.

Худший случай

Пусть опорным каждый раз оказывается минимум отрезка. Тогда левая половина пуста, правая короче исходной всего на один элемент, и глубина рекурсии становится $n$. Всего работы — $n + (n-1) + \ldots + 1$, то есть $O(n^2)$.

Именно поэтому опорный элемент берут случайным. Вероятность, что случайный выбор окажется минимумом на каждом шаге, — это $\tfrac{1}{n} \cdot \tfrac{1}{n-1} \cdot \ldots$, число настолько малое, что рассматривать его всерьёз незачем.

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

Почему в среднем n log n

Строгий разбор требует матожидания, но есть простое рассуждение на пальцах.

Разделим массив мысленно на четыре четверти по значению. Если случайный опорный попал в две средние четверти — а это происходит с вероятностью $\tfrac{1}{2}$, — то большая из половин занимает не больше $\tfrac{3}{4}$ массива.

Значит, примерно каждый второй шаг уменьшает задачу хотя бы в $\tfrac{4}{3}$ раза. Чтобы дойти от $n$ до единицы, таких удачных шагов нужно $\log_{4/3} n$, а всего шагов вдвое больше:

$$2 \, n \log_{4/3} n$$

Основание логарифма роли не играет: три деления на $\tfrac{4}{3}$ уменьшают массив больше чем вдвое, значит $\log_{4/3} n < 3 \log_2 n$. Всё вместе — $O(n \log n)$.

graph TD
  A["n элементов"] -->|"удачное разделение"| B["≤ 3n/4"]
  A -->|"неудачное"| C["почти n"]
  B --> D["≤ 9n/16"]
  C --> E["≤ 3n/4"]
  D --> F["…"]
  E --> F
  F --> G["1"]

Много одинаковых элементов

У разделения на две части есть слабое место: если в массиве много повторов, элементы, равные опорному, распределяются между половинами как придётся, и обе половины остаются большими.

В крайнем случае — массив из одинаковых чисел — разделение всегда идёт примерно пополам, что не плохо, но каждый уровень рекурсии не убирает ни одного элемента насовсем: равные опорному продолжают участвовать в сортировке снова и снова.

Лечится разделением на три части: меньше опорного, равные ему, больше. Средняя часть уже отсортирована, и рекурсия в неё не идёт.

// Разбиение на три части: [l, lt) меньше x, [lt, gt) равны, [gt, r) больше.
void quick_sort3(vector<int>& a, int l, int r) {
    if (r - l <= 1) return;
    int x = a[l + rand() % (r - l)];
    int lt = l, i = l, gt = r;
    while (i < gt) {
        if (a[i] < x) swap(a[lt++], a[i++]);
        else if (a[i] > x) swap(a[i], a[--gt]);
        else i++;
    }
    quick_sort3(a, l, lt);
    quick_sort3(a, gt, r);
}

Этот приём известен как «задача о голландском флаге»: три цвета надо разложить по трём зонам за один проход. На массиве, где различных значений мало, разница с двухпутевым разделением получается драматической — из $O(n \log n)$ работа падает до $O(n \cdot d)$, где $d$ — число различных значений.

Можно ли гарантировать

Да, и приём стоит запомнить. Если разделение вышло совсем перекошенным — скажем, хуже чем 25 на 75, — можно просто позвать partition заново с другим случайным опорным.

Вероятность неудачи на одной попытке около $\tfrac{1}{2}$, значит в среднем хватает двух попыток. А вероятность, что тридцать попыток подряд окажутся неудачными, — примерно одна миллиардная. Формально это по-прежнему не гарантия, но событие менее вероятное, чем большинство тех, о которых мы не беспокоимся.