Практика 25 сентября. Мастер-теорема, быстрая сортировка, нижняя оценка сортировок

Практика после лекций про сортировку слиянием и быструю сортировку. Сначала — мастер-теорема: как по рекуррентному соотношению сразу получить асимптотику рекурсивного алгоритма и почему у слияния выходит $n\log n$. Потом подробный разбор быстрой сортировки: два способа разбиения, выбор опорного элемента, время и память. Разбиения Хоара и Ломуто на тестах и коллоквиумах путают особенно часто. В конце доказано, что никакая сортировка сравнениями не работает в худшем случае быстрее $n\log n$.

1. Мастер-теорема

1.1. Рекуррентное соотношение

Алгоритм «разделяй и властвуй» делит задачу размера $n$ на части, рекурсивно решает некоторые из них и что-то делает сам. Время его работы описывается соотношением $T(n)=a\cdot T\!\left(\frac nb\right)+f(n).$

Обычно $f(n)$ — многочлен, и оценивают его старшей степенью: $f(n)=\Theta(n^c)$. Если $f$ не многочлен, её ограничивают подходящим многочленом; есть и общая версия теоремы, до неё курс дойдёт позже.

В слиянии обе половины сортируются рекурсивно, поэтому $a=2$. В бинарном поиске массив тоже делится пополам, но дальше работаем только с одной половиной — $a=1$. Параметр $b$ показывает, какая часть массива приходится на один вызов: в обоих случаях половина, $b=2$.

1.2. Дерево рекурсии

Нарисуем вызовы деревом. Корень — задача размера $n$, у каждого узла $a$ детей размера в $b$ раз меньше.

Размер уменьшается в $b$ раз, пока не станет $1$, поэтому уровней $\log_bn+1$. Складываем работу по уровням: $T(n)=n^c\sum_{i=0}^{\log_bn}q^i,\qquad q=\frac a{b^c}.$ Это геометрическая прогрессия, и ответ зависит только от того, сравнима ли $q$ с единицей.

1.3. Три случая

$q=1$, то есть $a=b^c$. На каждом уровне делается одинаковая работа $n^c$ — от числа уровней она не зависит. Сумма — это $\log_bn+1$ единиц: $T(n)=\Theta(n^c\log n).$ Основание логарифма не пишут: $\log_bn=\frac{\log_2n}{\log_2b}$, логарифмы по разным основаниям отличаются в константу раз.

$q<1$, то есть $a<b^c$. Работа убывает от корня к листьям, и самый «жирный» уровень — корень. Сумма ограничена константой: $\sum_{i\ge0}q^i=\frac1{1-q},\qquad T(n)=\Theta(n^c).$ Даже если $q=0{,}999$, сумма не больше $1000$ — огромная, но константа, и асимптотику она не меняет.

$q>1$, то есть $a>b^c$. Работа растёт к листьям, самый тяжёлый уровень — нижний, и сумма с точностью до константы равна последнему слагаемому: $n^c\,q^{\log_bn}=n^c\cdot\frac{a^{\log_bn}}{\left(b^{\log_bn}\right)^c}=n^c\cdot\frac{a^{\log_bn}}{n^c}=a^{\log_bn}=n^{\log_ba}.$ Последнее равенство — логарифмирование: $\log_b\big(a^{\log_bn}\big)=\log_bn\cdot\log_ba=\log_b\big(n^{\log_ba}\big)$. Итак, $T(n)=\Theta(n^{\log_ba})$.

То же самое удобно помнить как сравнение $c$ с $\log_ba$: какое из двух чисел больше, та степень и побеждает, а при равенстве добавляется логарифм.

Примеры.

• Слияние: $a=2$, $b^c=2^1=2$ — случай $a=b^c$, $T(n)=\Theta(n\log n)$.
• Бинарный поиск: $a=1=2^0$ — тоже равенство, $T(n)=\Theta(n^0\log n)=\Theta(\log n)$.
• $T(n)=T\big(\frac n2\big)+n$: $a=1<2$ — работа в корне, $n+\frac n2+\frac n4+\dots<2n$, $T(n)=\Theta(n)$.
• $T(n)=4T\big(\frac n2\big)+n$: $a=4>2$ — работа в листьях, $T(n)=\Theta(n^{\log_24})=\Theta(n^2)$. Третий случай может давать и $n^2$, и $n^3$, и дробные степени: при $a=3$, $b=2$, $c=1$ получается $n^{\log_23}\approx n^{1{,}585}$.

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

2.1. Идея: работа на спуске

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

В быстрой сортировке наоборот, работа делается на спуске. Выбирается опорный элемент $p$, и массив разбивается так, чтобы слева оказались элементы $\le p$, а справа — элементы $\ge p$. Затем каждая часть сортируется рекурсивно. На подъёме делать ничего не нужно: части уже стоят в правильном порядке относительно друг друга.

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

2.2. Разбиение Хоара

Два равноправных указателя идут навстречу друг другу с двух концов:

• $i$ идёт слева направо и останавливается на элементе $\ge p$ — он «не на своей половине»;
• $j$ идёт справа налево и останавливается на элементе $\le p$;
• если $i\le j$, элементы меняются местами, и оба указателя сдвигаются дальше;
• так продолжается, пока указатели не пересекутся.

После этого элементы с индексами от начала до $j$ не больше $p$, а от $i$ до конца — не меньше $p$.

Пример. Массив $7,1,8,3,5,4,9,2,6$, опорный $p=5$ (взят из середины — только для наглядности).

Теперь $i=5$, $j=3$ — указатели пересеклись. Слева $2,1,4,3\le5$, справа $8,9,7,6\ge5$, и рекурсия запускается от $[0;3]$ и $[5;8]$.

void quick_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    int p = a[l + rand() % (r - l + 1)];  // опорный — любой, здесь случайный
    int i = l, j = r;
    while (i <= j) {
        while (a[i] < p) i++;   // стоп на элементе >= p
        while (a[j] > p) j--;   // стоп на элементе <= p
        if (i <= j) swap(a[i++], a[j--]);
    }
    quick_sort(a, l, j);        // a[l..j] <= p
    quick_sort(a, i, r);        // a[i..r] >= p
}

2.3. Разбиение Ломуто

Указатели неравноправны и идут в одну сторону:

• $i$ — граница: всё левее $i$ меньше опорного;
• $j$ просто проходит по массиву;
• если $a_j<p$, то $a_j$ меняется с $a_i$, и граница $i$ сдвигается вправо.

В классической записи опорный сначала переставляют в конец, а после прохода ставят на место $i$ — на границу между частями.

Пример. Тот же массив и тот же опорный $5$. Переставляем $5$ в конец: $7,1,8,3,6,4,9,2,\underline5$, $i=0$.

В конце меняем $a_4$ с опорным: $1,3,4,2,\mathbf5,8,9,7,6$. Пятёрка стоит на индексе $4$ — ровно там же, где в отсортированном массиве $1,2,\dots,9$.

void quick_sort(vector<int>& a, int l, int r) {
    if (l >= r) return;
    swap(a[l + rand() % (r - l + 1)], a[r]);  // опорный — в конец
    int p = a[r];
    int i = l;                                // a[l..i-1] < p
    for (int j = l; j < r; j++)
        if (a[j] < p) swap(a[i++], a[j]);
    swap(a[i], a[r]);                         // опорный на своё место
    quick_sort(a, l, i - 1);
    quick_sort(a, i + 1, r);
}

Студенты, сравнивавшие обе схемы бенчмарками, иногда получают, что Ломуто быстрее, хотя классически быстрее считается Хоар. Преподаватель посоветовал статью на Хабре о том, как Ломуто можно оптимизировать под современные процессоры, — в том числе поэтому его и изучают.

2.4. Чем отличаются Хоар и Ломуто

Вопрос «в чём разница между разбиениями Хоара и Ломуто» любят задавать на тестах и коллоквиуме: ответ короткий и сразу показывает, понимаете ли вы тему. Правильный ответ:

• разница только в принципе разбиения;
• в Хоаре два равноправных указателя идут с разных сторон и меняют местами элементы, стоящие не в своей половине;
• в Ломуто один указатель отвечает за границу элементов меньше опорного, другой проходит по массиву.

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

2.5. Время работы

Лучший случай — разбиение каждый раз пополам. Это то же дерево, что у слияния: $T(n)=2T\big(\frac n2\big)+\Theta(n)=\Theta(n\log n)$.

Средний случай — тоже $\Theta(n\log n)$, даже если разбиение неровное. Пусть массив каждый раз делится в отношении $\frac1{10}:\frac9{10}$. Самая длинная ветвь — та, где каждый раз отрезается лишь десятая часть. Её глубина $\log_{10/9}n$, то есть снова логарифм, только по другому основанию, а основание — константа. На каждом уровне в сумме обрабатывается не больше $n$ элементов, поэтому время $O(n\log n)$.

Худший случай — опорным каждый раз оказывается минимум или максимум. Тогда массив делится на $1$ и $n-1$, потом на $1$ и $n-2$, и так далее: глубина рекурсии $n$, а работа $n+(n-1)+(n-2)+\dots+1=\frac{n(n+1)}2=\Theta(n^2).$

2.6. Выбор опорного элемента

Медиана из трёх: для массива, где первый элемент $4$, средний $5$, последний $9$, опорным станет $5$. Он гарантированно не минимум и не максимум массива, если только все три не равны.

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

2.7. Память и устойчивость

Память. Быстрой сортировке не нужен буфер: всё переставляется на месте, а на подъёме нечего сливать. Память уходит только на стек рекурсии, и её объём — это глубина рекурсии. У слияния стек тоже есть, но $O(\log n)$ несопоставимо меньше буфера на $n$ элементов, поэтому память слияния — $O(n)$.

Устойчивость. Сортировка устойчива, если элементы с равными ключами сохраняют исходный порядок. Быстрая сортировка неустойчива: обмены переносят элементы через большие расстояния, и равные элементы могут поменяться местами. На каком-то конкретном массиве порядок равных может и сохраниться, но это не гарантировано — а устойчивость означает именно гарантию.

3. Нижняя оценка сортировок сравнением

3.1. Дерево решений

Сортировки вставками, слиянием и быстрая сравнивают элементы попарно и в зависимости от ответа что-то переставляют. Такие сортировки называются сортировками сравнением. Их все можно описать одной моделью, не вникая, рекурсивный алгоритм или итеративный.

Дерево решений.

• Узел — состояние алгоритма: текущий порядок элементов и все его переменные.
• В каждом узле алгоритм задаёт вопрос «$a_i<a_j$?». В зависимости от ответа «вселенная расщепляется» на две ветки, и алгоритм переходит в одно из двух новых состояний.
• Лист — конец работы: алгоритм выдал ответ, то есть перестановку исходного массива, которая делает его отсортированным.

Работа алгоритма на конкретном входе — путь от корня к листу, а число сравнений — длина этого пути. Время в худшем случае не меньше высоты дерева.

3.2. Высота не меньше логарифма факториала

Каждая из $n!$ перестановок входного массива требует своего ответа, поэтому листьев не меньше $n!$. У двоичного дерева высоты $h$ не больше $2^h$ листьев: самое низкое дерево — полное, где на каждом следующем уровне вдвое больше узлов. Значит, $2^h\ge n!\quad\Rightarrow\quad h\ge\log_2n!.$

Оценим $\log_2n!$ с двух сторон.

• Сверху: $n!=1\cdot2\cdots n\le n\cdot n\cdots n=n^n$, поэтому $\log_2n!\le n\log_2n$.
• Снизу: в произведении $1\cdot2\cdots n$ последние $\frac n2$ множителей не меньше $\frac n2$, а остальные не меньше $1$, поэтому $n!\ge\left(\frac n2\right)^{n/2}$ и $\log_2n!\ge\frac n2\log_2\frac n2=\frac n2\big(\log_2n-1\big).$

Обе оценки — это $n\log n$ с точностью до константы, значит, $\log_2n!=\Theta(n\log n)$.

Теорема. Любая сортировка сравнением в худшем случае делает $\Omega(n\log n)$ сравнений.

Поэтому сортировка слиянием асимптотически оптимальна среди сортировок сравнением, и никакая хитрость не даст, например, $O(n\log\log n)$ в худшем случае.

Числа: $n=10$ — перестановок $10!=3\,628\,800$, $\log_2 10!\approx21{,}8$. Любой алгоритм сравнения на каком-то входе из $10$ элементов делает не меньше $22$ сравнений.

3.3. Компараторы

Сортировкам сравнением не важно, что именно сортируется: достаточно уметь для двух объектов ответить, какой из них должен стоять левее. Математически это отношение линейного порядка, а в C++ — компаратор: функция, которая принимает два объекта и возвращает bool.

enum Color { Red, Orange, Yellow, Green, Blue, Indigo, Violet };  // порядок цветов радуги
 
bool by_rainbow(Color x, Color y) {
    return x < y;              // true, если x должен стоять левее y
}
 
sort(colors.begin(), colors.end(), by_rainbow);

Так можно отсортировать числа, строки в лексикографическом порядке, цвета радуги и любые свои объекты — задав компаратор или перегрузив для типа оператор <. Любая сортировка сравнением работает с ними без изменений.

Если же сортируются целые числа (или объекты по целочисленному ключу), можно не сравнивать элементы, а использовать их значения напрямую. Такие сортировки обходят оценку $n\log n$ — это линейные сортировки, следующая тема.

Частые ошибки

1. «В Хоаре опорный средний, в Ломуто последний». Выбор опорного не зависит от схемы разбиения; различается только работа указателей.
2. Путать, где делается работа. Слияние работает на подъёме рекурсии, быстрая сортировка — на спуске.
3. Считать $a$ по числу частей, а не вызовов. В бинарном поиске массив делится на две части, но рекурсивный вызов один: $a=1$, $b=2$.
4. Писать основание логарифма в асимптотике. $\log_2n$ и $\log_{10/9}n$ отличаются в константу раз — это одно и то же $\Theta(\log n)$.
5. Думать, что неровное разбиение портит асимптотику. При пропорции $1:9$ глубина всё равно логарифмическая. Плохо, когда разбиение даёт $1$ и $n-1$.
6. Брать опорный всегда из середины и считать это защитой. Против фиксированного выбора легко построить тест с $n^2$.
7. Говорить, что быстрая сортировка не использует доп. память. Буфера нет, но стек рекурсии — от $O(\log n)$ до $O(n)$.
8. Называть быструю сортировку устойчивой, потому что на примере порядок сохранился. Устойчивость — это гарантия для любого входа.
9. Считать, что нижняя оценка $n\log n$ касается всех сортировок. Она верна только для сортировок сравнением; для целых чисел есть линейные сортировки.

Мини-тренажёр

1. Найдите асимптотику: $T(n)=2T\big(\frac n2\big)+n^2$.
2. Найдите асимптотику: $T(n)=8T\big(\frac n2\big)+n^2$.
3. Найдите асимптотику: $T(n)=9T\big(\frac n3\big)+n^2$.
4. Сколько уровней у дерева рекурсии слияния для $n=1024$?
5. Выполните разбиение Хоара массива $4,9,2,7,5,1$ с опорным $p=5$. Где остановились указатели?
6. Выполните разбиение Ломуто массива $3,8,1,6,2$ с опорным $p=3$ (опорный уже первый — сначала переставьте его в конец).
7. Какова глубина рекурсии быстрой сортировки, если опорным всегда оказывается максимум? А если разбиение всегда $\frac14:\frac34$?
8. Медиана из трёх для массива $8,3,1,7,2$ — какой элемент станет опорным?
9. Сколько листьев минимум у дерева решений для сортировки $4$ элементов и какова минимальная высота?
10. Почему быстрая сортировка не противоречит нижней оценке, хотя в среднем тоже $n\log n$, а в худшем — $n^2$?

Шпаргалка