Занятие 21. Сортировки за n log n

Занятие 19 закончилось приговором: алгоритмы, переставляющие только соседей, платят Inv(a), то есть в среднем $\sim n^2/4$. Выход — дальнобойные перестановки: одно перемещение через полмассива гасит тысячи инверсий разом. Сегодня два классических способа делать это за $n \log n$ — фон Нейман (1945) и Хоар (1959), оба на каркасе «разделяй и властвуй» из занятия 6. Обозначения — как в весеннем конспекте сортировок; замеры реальные (Apple M-серия, clang++ -O2).

Две симметричные философии: merge sort делит тупо (пополам), а трудится при сборке; quicksort делит умно (по пивоту), и вся работа происходит при делении.

Сортировка слиянием

1
2
3
4
5
6
7
8

// сортирует полуинтервал a[l, r)
void mergeSort(std::vector<int>& a, int l, int r, std::vector<int>& buf) {
    if (r - l <= 1) return;            // база: один элемент
    int m = l + (r - l) / 2;
    mergeSort(a, l, m, buf);
    mergeSort(a, m, r, buf);
    merge(a, l, m, r, buf);            // слить два отсортированных
}

Дерево — то самое из занятия 6: $T(n) = 2\,T(n/2) + \Theta(n)$, случай $c = \log_b a$ мастер-теоремы, итого $\Theta(n \log n)$ на любом входе — у merge sort нет худшего случая.

merge: два указателя из занятия 12

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

// сливает отсортированные a[l, m) и a[m, r)
void merge(std::vector<int>& a, int l, int m, int r, std::vector<int>& buf) {
    int i = l, j = m, k = 0;
    while (i < m || j < r) {
        if (i == m || (j < r && a[i] > a[j]))
            buf[k++] = a[j++];         // берём справа
        else
            buf[k++] = a[i++];         // берём слева
    }
    for (int t = 0; t < r - l; t++) a[l + t] = buf[t];
}

На каждом шаге забираем меньшую из двух голов — метод двух указателей, Θ(n). Стабильность спрятана в одном символе: сравнение a[i] > a[j] строгое, поэтому при равных берём слева — порядок равных элементов не рвётся (занятие 19 объясняло, зачем это нужно). Плата — буфер: сливать на месте за Θ(n) нельзя.

Замер — и бонус, закрывающий звёздочку

# random, 10^7 элементов
merge sort:   746 мс   (буфер 40 МБ)

746 мс на $10^7$ — против ~8 часов экстраполяции для вставок: $n \log n$ против $n^2$ в полный рост. И бонус: тот же каркас считает инверсии за $n \log n$ — при взятии элемента из правой половины он меньше всех оставшихся слева, значит inv += m - i разом:

инверсии наивно O(n^2):  249152    # занятие 19, тот же массив
инверсии через merge:    249152    # сошлось до единицы

Звёздочка из ДЗ занятия 19 закрыта.

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

Идея Хоара — и школьная версия

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

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

// «школьная» версия — как в весеннем конспекте
std::vector<int> quickSort(std::vector<int> a) {
    if (a.size() <= 1) return a;
    int x = a[rand() % a.size()];          // случайный пивот
    std::vector<int> l, m, r;              // <x  ==x  >x
    for (int e : a)
        (e < x ? l : e == x ? m : r).push_back(e);
    auto L = quickSort(l), R = quickSort(r);
    L.insert(L.end(), m.begin(), m.end());
    L.insert(L.end(), R.begin(), R.end());
    return L;                          // L + m + R
}

Честно и понятно, но три вектора на каждом уровне: замер — 2114 мс на $10^7$.

In-place партиция: инвариант трёх зон

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

// пивот p стоит в a[r-1]
int p = a[r - 1], i = l;
// инвариант: [l, i) < p   |   [i, j) >= p   |   дальше не просмотрено
for (int j = l; j < r - 1; j++)
    if (a[j] < p)
        std::swap(a[i++], a[j]);           // расширить левую зону
std::swap(a[i], a[r - 1]);                 // пивот на своё место
// теперь: [l, i) < p, a[i] = p, (i, r) >= p
quickSort(a, l, i);
quickSort(a, i + 1, r);

Каждый шаг цикла сохраняет инвариант: если a[j] < p — обмен расширяет зелёную зону, иначе жёлтая растёт сама. Доказательство корректности — привычная схема занятия 12: инициализация, сохранение, завершение.

Средний случай

# random, 10^7
quicksort in-place:   606 мс
глубина рекурсии:      58      # ~2.5 · log2(10^7)

Случайный пивот в среднем делит массив в пропорции не хуже 1:3 — глубина $O(\log n)$, на каждом уровне суммарно Θ(n) работы. In-place быстрее школьной версии в 3.5 раза: ноль аллокаций, кэш доволен (занятие 8). Нестабильна: дальние свопы партиции рвут порядок равных — тот же механизм, что у сортировки выбором.

Худший случай: два killer-входа

Killer № 1: наивный пивот + отсортированный вход

# пивот = последний элемент, вход отсортирован, n = 50 000
пивот=последний:    347 мс     # квадрат!
случайный пивот:   0.86 мс     # ×400, глубина 35

Пивот-максимум отрезает по одному элементу: $T(n) = T(n-1) + \Theta(n)$ — знакомый квадрат, плюс глубина рекурсии $n$ с угрозой переполнения стека (занятие 5). Отсортированный вход — не экзотика, а самый частый вход в продакшене; наивный quicksort квадратичен ровно там, где данных больше всего. Случайный пивот делает худший случай астрономически маловероятным — и защищает даже от злонамеренно подобранного входа.

Killer № 2: все элементы равны

# ВСЕ элементы равны, n = 50 000
Ломуто + СЛУЧАЙНЫЙ пивот:   317 мс    # снова квадрат!
школьная версия (<, ==, >):  линейна

Сюрприз: случайность не спасает — при равных элементах никто не «меньше p», левая зона не растёт, партиция вновь отрезает по одному. А «наивная» школьная версия здесь линейна: трёхчастное разбиение отправляет всех в кучку «равно», рекурсии достаются пустяки. Мораль: «оптимизированный» и «правильный» — разные оси; взрослое лекарство — трёхчастная in-place партиция (задача голландского флага, звёздочка в ДЗ). Дубликаты — норма жизни: возрасты, оценки, статусы.

Три лекарства — и страховка std::sort

1. Случайный пивот — худший случай становится невоспроизводимым; цена — вызов генератора на партицию.
2. Медиана трёх (первый, средний, последний) — дёшево, детерминированно, убивает «отсортированный» killer; от подобранного входа не защищает.
3. Страховка introsort — считать глубину рекурсии; глубже $2 \log n$ — переключиться на heapsort с гарантией $n \log n$. Так std::sort обещает $n \log n$ всегда (занятие 19 упоминало эту конструкцию — теперь видно, зачем она).

Инженерный паттерн шире сортировок: быстрый в среднем алгоритм + дешёвый детектор беды + медленный, но гарантированный запасной.

Сводный замер

# random, 10^7 элементов, clang++ -O2
merge sort (наш):        746 мс   + 40 МБ буфер
quicksort in-place:      606 мс   in-place
quicksort «школьный»:   2114 мс   аллокации
std::sort:               166 мс
std::stable_sort:        166 мс

Наши честные реализации — в 4 раза медленнее std::sort: у него база-вставки на коротких кусках (занятие 19), медиана трёх и отточенные ветвления; асимптотика та же, константа вылизана десятилетиями.

* нужен порядок равных — std::stable_sort (merge-семейство). Сквозная мысль: merge продаёт память за гарантию, quick продаёт гарантию за память — introsort покупает обе, комбинируя три алгоритма.

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

1. Дерево слияний. Прогоните mergeSort на {5, 2, 4, 6, 1, 3}: дерево рекурсии и массив после каждого merge. Сколько всего сравнений? Сравните с $n \log_2 n$.

   Разбор

   Деление: {5,2,4} и {6,1,3} → {5},{2,4} и {6},{1,3}. Слияния снизу вверх: {2,4} (1 сравнение) → {2,4,5} (2) → {1,3} (1) → {1,3,6} (2) → финальное {1,2,3,4,5,6} (5 сравнений: 1<5? 2<3?…). Итого 11 сравнений при $n \log_2 n \approx 15.5$ — реальное число всегда ≤ теоретической оценки, потому что слияния кончаются раньше, когда одна половина исчерпана.

2. Партиция под микроскопом. Вход {3, 8, 2, 5, 1, 4}, пивот 4 (уже в конце). Таблица i, j и зон после каждого шага; где окажется пивот?

   Разбор

   Старт i=0. j=0: 3<4 — swap(a0,a0), i=1 → {3|8,2,5,1|4}. j=1: 8≥4 — жёлтая растёт. j=2: 2<4 — swap(a1,a2), i=2 → {3,2|8,5,1|4}. j=3: 5≥4. j=4: 1<4 — swap(a2,a4), i=3 → {3,2,1|5,8|4}. Финальный swap(a3, a5): {3,2,1,4,8,5} — пивот на позиции 3, слева всё меньше, справа всё не меньше. Инвариант держался в каждой строке.

3. Сломайте медиану трёх. Постройте вход из 7 элементов, где пивот-медиана(первый, средний, последний) делит массив хуже, чем 1:5.

   Разбор

   Нужно, чтобы медиана трёх оказалась почти минимумом или максимумом всего массива. Пример: {2, 7, 6, 3, 5, 4, 1}: тройка (2, 3, 1) → медиана 2 — второй наименьший элемент, партиция 1:5. Конструкция обобщается: ставим три малых значения на позиции «первый, средний, последний», остальное — большое; известная семья «median-of-3 killer» строит такие входы для любого n — поэтому медиана трёх лечит случайные беды, но не противника.

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

1. Обе сортировки со счётчиками сравнений; сверьте счётчики с $n \log_2 n$ на $n = 10^3, 10^4, 10^5$.
2. Инверсии за n log n через merge — та самая звёздочка занятия 19; стресс-тест против наивного $O(n^2)$.
3. Killer-лаборатория: таблица времён вашего quicksort на четырёх входах (random / sorted / reversed / все равны) × двух пивотах (последний / случайный); объясните каждую клетку.
4. Стабильность: покажите на парах (ключ, номер), что ваш merge стабилен, а quicksort — нет; укажите строку кода, отвечающую за каждое.
5. * Трёхчастная партиция (задача голландского флага) in-place: < p | = p | > p; замерьте на массиве из 10 различных значений против обычной партиции.

Следующее занятие — move-семантика: lvalue и rvalue, ссылки со «вторым амперсандом», std::move и куда на самом деле «переезжает» вектор. А сортировки без сравнений — k-я статистика, нижняя оценка Ω(n log n), counting и radix — вернутся на семинаре 23.