Занятие 19. Квадратичные сортировки

Первые честные сортировки курса: два алгоритма, у каждого — инвариант, который можно выписать и доказать (занятия 5 и 12 нас к этому готовили). Квадратичные сортировки — не музей: они система отсчёта для n log n ближайшего семинара сортировок, база рекурсии внутри промышленных сортировок и чемпионы на почти отсортированных данных. Замеры реальные (Apple M-серия, clang++ -O2).

Сортировка выбором

Найти минимум остатка — поставить в конец готового префикса — забыть о нём.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void selectionSort(std::vector<int>& a) {
    int n = a.size();
    // инвариант: a[0..i) отсортирован и содержит i НАИМЕНЬШИХ элементов
    for (int i = 0; i < n - 1; i++) {
        int mn = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[mn]) mn = j;
        std::swap(a[i], a[mn]);       // элемент встал НАВСЕГДА
    }
}

Инвариант сильный: готовый префикс — окончательный. Сохранение: минимум остатка не меньше любого элемента префикса, значит, поставить его в конец префикса безопасно. Завершение: $i$ дошло до $n-1$ — массив отсортирован. Схема доказательства — та же, что у бинпоиска в занятии 12.

Портрет: слепой, но экономный на записи

# счётчики, n = 1000
вход       сравнений   обменов
sorted        499500         0
random        499500       996
reversed      499500       500

Сравнений — ровно $n(n-1)/2$ на любом входе: 499 500 и на отсортированном, и на перевёрнутом. Алгоритм слеп к порядку — он в любом случае сканирует весь хвост. Зато обменов не больше $n-1$: меньше записей не делает почти никто. Ниша — дорогая запись при дешёвом чтении: флеш-память с износом, огромные объекты с дешёвым сравнением.

Нестабильна: на $[5_1, 5_2, 3, 1]$ первый же обмен уносит $5_1$ за $5_2$: $[1, 5_2, 3, 5_1]$ — дальний swap рвёт порядок равных (почему это важно — занятие 17, каскадные сортировки).

Сортировка вставками

Как раскладывают карты: очередной элемент вдвигается в отсортированную часть на своё место.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void insertionSort(std::vector<int>& a) {
    int n = a.size();
    // инвариант: a[0..i) отсортирован (это те же первые i элементов входа)
    for (int i = 1; i < n; i++) {
        int x = a[i], j = i - 1;
        while (j >= 0 && a[j] > x) {
            a[j + 1] = a[j];          // сдвиг вправо
            j--;
        }
        a[j + 1] = x;                 // вставка на место
    }
}

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

Портрет: адаптивный и стабильный

# счётчики, n = 1000
вход       сравнений    сдвигов
sorted           999          0
random        250145     249152
reversed      499500     499500

Диапазон огромен: от $n-1$ сравнений и нуля сдвигов на отсортированном входе до $n(n-1)/2$ на перевёрнутом. Время зависит от входа — алгоритм адаптивен. Стабилен: меняются местами только соседи, образующие инверсию, — равные элементы никогда не перепрыгивают друг друга. И бонус: элементы можно получать по одному — сортировка «на лету» (инвариант «всё пришедшее отсортировано» держится после каждой вставки).

Инверсии: валюта беспорядка

Максимум — перевёрнутый массив, все $n(n-1)/2$ пар. Случайный — в среднем половина пар испорчена: $n(n-1)/4$. Проба на $n = 1000$: насчитали 249 152 при теоретических 249 750. Inv(a) превращает «на глаз почти отсортирован» в конкретное число.

Это нижняя граница на целый класс алгоритмов — тем же жанром, что нижние оценки занятия 2: не «мы не придумали быстрее», а «быстрее не бывает».

Вставки платят ровно по счёту

# random, n = 1000
инверсий во входе:      249152
сдвигов у insertion:    249152   # РОВНО столько

Каждый сдвиг убирает ровно одну инверсию — счётчики совпали до единицы, теорема живьём. Итого $\Theta(n + \operatorname{Inv}(a))$: $n$ на проход, Inv на сдвиги. В классе «соседних» алгоритмов вставки оптимальны — меньше, чем Inv(a), не заплатит никто.

Отсюда же ответ, как побеждать квадрат: только выйдя из класса — переставлять далёкие элементы, убирая много инверсий за одно перемещение. Случайный вход несёт $\sim n^2/4$ инверсий, поэтому средний случай любых «соседних» сортировок неизбежно квадратичен; merge sort и quicksort (семинар занятия 21) потому и быстры, что дальнобойны.

Замеры

Увидеть Θ(n²) глазами

# random, clang++ -O2
n =  5000: selection   34.6 мс | insertion   2.8 мс
n = 10000: selection   88.4 мс | insertion   7.4 мс
n = 20000: selection  295.5 мс | insertion  29.1 мс

              std::sort: 0.08 / 0.14 / 0.27 мс

Удвоение $n$ — время ×3–4: квадрат виден в живых числах (идеальные ×4 смазывают кэши; методика замеров — занятие 16). Вставки при равном «O» быстрее выбора в разы: их работа соседняя, кэш и предсказатель переходов довольны (занятие 8). А std::sort на 20 000 элементах быстрее обоих на два-три порядка: n log n против n² — не спор, а разгром.

Гвоздь: почти отсортированные данные

$n = 100\,000$: отсортированный массив плюс 20 случайных обменов — инверсий мало.

insertion:   0.37 мс   # Θ(n + Inv) ≈ линейно
std::sort:   0.17 мс
selection:  ~7 секунд  # экстраполяция ×25 от замера n = 20000

Вставки на почти отсортированном линейны и играют в одной лиге с промышленным std::sort. Выбор слеп: свои $n(n-1)/2$ сравнений он отработает при любом входе — разница со вставками ×20 000. Почти отсортированные данные — не экзотика: дозаписанные логи, обновлённые рейтинги, вчерашний отсортированный файл плюс новые записи. И проверка стоит копейки: std::is_sorted — O(n).

Вставки живут внутри каждого sort

std::sort — это introsort: quicksort + страховка heapsort + сортировка вставками для коротких кусков (порядка пары десятков элементов). Почему именно вставки: после разбиений куски маленькие и почти упорядоченные — мало инверсий; работа соседняя — кэшу хорошо; накладные расходы рекурсии дороже честного маленького квадратика. Timsort (Python, Java) построен на той же идее: находит отсортированные куски и доращивает их вставками.

Итог одной фразой: «квадратичная» ≠ «бесполезная» — это специалисты узкого профиля. Выбор — когда запись дорога; вставки — когда беспорядка мало. Универсалы n log n — на семинаре занятия 21.

Задачи семинара

1. Трассировка. Отсортируйте вставками {5, 2, 4, 6, 1, 3} на бумаге: массив после каждого $i$; сколько всего сдвигов? Проверьте, пересчитав инверсии входа.

   Разбор

   Ходы: {2,5,4,6,1,3} (1 сдвиг) → {2,4,5,6,1,3} (1) → {2,4,5,6,1,3} (0: 6 уже на месте) → {1,2,4,5,6,3} (4) → {1,2,3,4,5,6} (3). Всего 9 сдвигов. Инверсии входа: (5,2),(5,4),(5,1),(5,3),(2,1),(4,1),(4,3),(6,1),(6,3) — тоже 9. Совпадение обязано быть точным: каждый сдвиг гасит ровно одну инверсию.

2. Суд над стабильностью. На $[5_1, 5_2, 3, 1]$ покажите по шагам, где выбор рвёт порядок пятёрок, и объясните, почему у вставок это невозможно в принципе.

   Разбор

   Выбор, шаг i=0: минимум 1 стоит в конце, swap с $5_1$ → $[1, 5_2, 3, 5_1]$ — $5_1$ перепрыгнул $5_2$, порядок равных нарушен ещё до конца сортировки, и дальше он не восстановится. У вставок обмены только соседние и только при строгой инверсии a[j] > x: равный сосед не сдвигается (условие строгое), поэтому равные элементы никогда не меняются местами.

3. Экстремали. Постройте входы длины $n$, где вставки делают: (1) минимум работы; (2) максимум; (3) ровно $(n-1) + k$ сравнений при $k$ сдвигах для небольшого $k$.

   Разбор

   (1) Отсортированный вход: $n-1$ сравнений, 0 сдвигов — каждая вставка обрывается на первом сравнении. (2) Перевёрнутый: $n(n-1)/2$ и сравнений, и сдвигов — каждая вставка пробивает весь префикс. (3) Возьмите отсортированный массив и перенесите один элемент на $k$ позиций влево — он образует ровно $k$ инверсий с перепрыгнутыми соседями, значит будет ровно $k$ сдвигов. Общее описание семейства: любой вход с $\operatorname{Inv}(a) = k$.

Домашнее задание (сдача через Git)

1. Обе сортировки со счётчиками сравнений и перемещений; воспроизведите таблицы семинара (n = 1000, входы sorted/random/reversed) и убедитесь: сдвиги вставок = инверсии входа.
2. Квадрат на графике: времена обеих сортировок для $n = 1000 \cdot 2^k$ по методике занятия 16; таблица «n → время → отношение к предыдущему».
3. Порог гибрида: найдите экспериментально длину B, до которой ваши вставки обгоняют std::sort на случайных данных вашей машины; таблица замеров вокруг порога.
4. Число инверсий наивно за $O(n^2)$ + стресс-тест против счётчика сдвигов вашей insertionSort.
5. * Расследование: найдите в исходниках libc++ (или libstdc++) порог переключения sort на вставки; приложите ссылку на строку и само число — и сравните с вашим порогом из задания 3.

Следующее занятие — std::variant и std::any: типобезопасный наследник union, обещанный занятием 18, и полиморфизм без наследования. А сортировки за n log n вернутся на семинаре 21: слиянием и быстрая, «разделяй и властвуй» из занятия 6 в главной роли.