Квадратичные сортировки

Написать std::sort(a.begin(), a.end()) быстрее, чем любую из сортировок этой статьи, и работать оно будет тоже быстрее. Тем не менее разбирать их стоит, и вот почему.

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

Пузырёк

Идём по массиву слева направо и меняем местами каждую пару соседей, стоящую в неверном порядке.

Возьмём массив 5 1 4 3 6 1 2. Сравниваем 5 и 1 — меняем. Потом 5 и 4 — меняем. Потом 5 и 3 — меняем. Потом 5 и 6 — оставляем. Потом 6 и 1 — меняем. Потом 6 и 2 — меняем. Один проход закончен, и максимум уехал в конец:

5 1 4 3 6 1 2   →   1 4 3 5 1 2 6

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

Один такой проход назовём эпохой. Сколько эпох нужно? Не $n$ и не $n/2$ — проверьте на массиве 4 3 2 1, половины эпох не хватит. Нужно $n - 1$: когда $n-1$ элементов стоят на своих местах, последнему просто некуда деться.

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

for (int epoch = 0; epoch < n - 1; epoch++)
    for (int i = 0; i < n - epoch - 1; i++)
        if (a[i] > a[i + 1]) swap(a[i], a[i + 1]);

Обратите внимание на n - epoch - 1, а не n - epoch: без единицы последняя итерация внутреннего цикла заглянет за границу массива.

Сравнений получается примерно $n^2/2$ — вдвое меньше, чем в лоб, но это константа, и асимптотика всё та же $O(n^2)$.

Обменов ровно столько, сколько инверсий

Полезный факт, который пригодится дальше. Каждый обмен пузырька меняет местами двух соседей, стоящих в неверном порядке, — то есть убирает ровно одну инверсию (пару $i < j$ с $a_i > a_j$) и не трогает остальные.

Значит, число обменов равно числу инверсий в исходном массиве. Это и объясняет, почему пузырёк медленный: инверсий бывает до $\tfrac{n(n-1)}{2}$, а он убирает их по одной.

Ту же величину умеет считать сортировка слиянием — но за $n \log n$, потому что убирает инверсии не по одной, а целыми группами. Подробнее в статье про слияние.

Вставки

Здесь идея другая, и она пригождается в других задачах.

Поддерживаем инвариант — условие, которое выполняется всегда: после $x$ проходов первые $x$ элементов отсортированы. Берём следующий элемент и двигаем его влево, пока слева стоит кто-то больший.

Пусть отсортированный префикс — это 1 3 10 12 15, а следующий элемент — 4. Сравниваем 4 и 15 — меняем. 4 и 12 — меняем. 4 и 10 — меняем. 4 и 3 — стоп: слева всё отсортировано, значит и всё остальное меньше четвёрки.

for (int i = 1; i < n; i++)
    for (int j = i; j > 0 && a[j - 1] > a[j]; j--)
        swap(a[j - 1], a[j]);

То же на Python — сдвигом вместо обменов, так короче и быстрее:

for i in range(1, n):
    value = a[i]
    j = i - 1
    while j >= 0 and a[j] > value:
        a[j + 1] = a[j]
        j -= 1
    a[j + 1] = value

Порядок условий в while — не вкусовщина

В условии j > 0 && a[j - 1] > a[j] порядок обязателен. C++ вычисляет && лениво: если левая часть ложна, правую он не считает. Поменяйте местами — и при j == 0 программа сначала обратится к a[-1], а проверку j > 0 сделает уже после. Слишком поздно.

То же и с ||: если левая часть истинна, правая не вычисляется. На этом держится половина проверок вида if (i < n && a[i] == x).

Чем вставки лучше пузырька

Лучший случай у вставок — $O(n)$: на уже отсортированном массиве каждый элемент сразу стоит на месте. Худший — $O(n^2)$, когда массив отсортирован по убыванию.

Но главное свойство другое. Пусть у вас уже отсортированный массив, и справа дописали один элемент. Вставкам достаточно провести его влево — это $O(n)$. Пузырьку придётся запускаться целиком заново, за $O(n^2)$.

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

Где это выигрывает у sort

Задача: в массиве из $n$ чисел найти сто наибольших.

Решение: держим массив-ответ длиной сто, отсортированный. Для каждого нового числа делаем push_back, проводим его влево одной итерацией вставки и, если размер стал 101, выбрасываем лишний элемент.

Получается $O(100n)$ — формально хуже, чем $O(n \log n)$ у сортировки, ведь $\log_2 10^6$ это всего 20. Но на практике эта версия быстрее: сто чисел лежат подряд и целиком помещаются в кеш процессора, а сортировка миллиона элементов гуляет по всей памяти.

Это не значит, что вставками надо сортировать массивы на $10^5$. Это значит, что асимптотика — не единственное, что определяет время.

Выбор

Самая простая из трёх. Находим минимум и ставим его на первое место. Находим минимум среди оставшихся — на второе. И так $n-1$ раз: последнему элементу выбора не остаётся.

for (int i = 0; i < n - 1; i++) {
    int j = min_element(a.begin() + i, a.end()) - a.begin();
    swap(a[i], a[j]);
}

min_element живёт в заголовке <algorithm>, принимает два итератора и возвращает итератор на минимальный элемент, а не индекс. Чтобы получить индекс, из него вычитают a.begin().

В отличие от вставок, выбор всегда работает за $O(n^2)$ — даже на отсортированном массиве, потому что минимум всё равно приходится искать проходом.

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

Итог

	Лучший случай	Худший	Что умеет
Пузырёк	$O(n^2)$	$O(n^2)$	ничего особенного
Вставки	$O(n)$	$O(n^2)$	держит порядок при дописывании справа
Выбор	$O(n^2)$	$O(n^2)$	превращается в $O(n \log n)$ заменой поиска минимума

Из трёх запоминать стоит вставки.