АиСД L05 - Быстрая сортировка и сортировка подсчётом

О чём лекция

Сортировка слиянием работает за $O(N\log N)$, но платит за скорость буфером на $O(N)$. Быстрая сортировка обходится без буфера: она делит массив не пополам по позиции, а по значению — на «меньше опорного» и «больше опорного». Лекция разбирает две схемы такого деления, Ломуто и Хоара, и объясняет, почему при неудачном выборе опорного элемента быстрая сортировка вырождается в $O(N^2)$. Во второй части — сортировка подсчётом: она вообще не сравнивает элементы и поэтому обходит нижнюю оценку $\Omega (N\log N)$.

Как читать

Доказательства в блоках «Не из лекции» дописаны к конспекту: на лекции их не было. Всё остальное — с доски. В рукописи есть ошибки, они отмечены блоками [!warning] и проверены запуском на C++.

Маршрут

1. Две сортировки за $N\log N$ → Сортировка слиянием, Быстрая сортировка
2. Схема Qsort и Partition
3. Выбор опорного элемента
4. Partition Ломуто
5. Partition Хоара
6. Асимптотика: лучший и худший случай → Асимптотические оценки, Рекурсия
7. Сортировка подсчётом → Сортировка подсчётом
8. Устойчивая сортировка подсчётом
9. Теорема о нижней оценке → нижняя оценка
10. «Сортировка за O(1)»

1. MergeSort и QuickSort

	$T(N)$	$M(N)$
Merge Sort	$O(N\log N)$	$O(N)$
Quick Sort	$O(N\log N{)}^{\ast }$	$O(1)$

Звёздочка у Quick Sort на доске не расшифрована. По разделу 6 она значит «при удачном разбиении»: в худшем случае время $O(N^2)$.

Разные сортировки → разные константы. Одинаковая асимптотика не значит одинаковую скорость: у быстрой сортировки нет копирования в буфер и обратно, и на практике она обычно быстрее.

$M(N)=O(1)$ — только без учёта рекурсии

Partition действительно работает на месте, без буфера. Но Qsort рекурсивен, и стек вызовов занимает память по глубине рекурсии (см. Рекурсия): $O(\log N)$ при разбиении пополам и $O(N)$ в худшем случае из раздела 6. Честная запись — $M(N)=O(\log N)$ в среднем, $O(N)$ в худшем.

Не из лекции

Худший случай по памяти можно убрать: рекурсивно вызываться только на меньшую часть, а большую обрабатывать циклом. Тогда глубина не больше ${\log }_{2}N$ — каждый рекурсивный вызов получает не больше половины.

2. Qsort

Partition

Берём в массиве опорный элемент (pivot) и переставляем элементы так, чтобы слева от него оказались все ≤ pivot, справа — все > pivot:

[▧|                 ]         ▧ — pivot
          ⇓
[ ≤ pivot  |▧|  > pivot ]
          ⇓
возвращает id pivot

Partition возвращает индекс, на котором оказался опорный элемент. На этом месте он и останется в отсортированном массиве: все левее не больше его, все правее — больше.

Рекурсия

Считаем на полуинтервале [left; right):

Qsort(arr, left, right)
    если left ≥ right
        return
    id_p = Partition(arr, left, right)
    Qsort(arr, left, id_p)
    Qsort(arr, id_p + 1, right)

              left              right
arr = [      |▨▨▨▨▨▨▨▨▨▨▨▨▨▨▨▨|      ]
                    ⇓
             [ ≤ p |p| > p ]
               ↓    id   ↓
       Qsort(left, id_p)  Qsort(id_p + 1, right)

Опорный элемент уже на своём месте, поэтому в рекурсию он не попадает: левая часть [left, id_p), правая [id_p + 1, right).

Не из лекции: доказательство правильности

Сильная индукция по длине $\ell =right-left$.

• $\ell \le 1$: ноль или один элемент уже отсортирован. Для $\ell =0$ срабатывает left ≥ right. При $\ell =1$ условие ложно, но Partition одного элемента возвращает left, и обе рекурсивные части пустые.
• $\ell \ge 2$: после Partition в [left, id_p) лежат элементы $\le p$, на id_p — сам $p$, в [id_p + 1, right) — элементы $>p$. Обе части короче $\ell$ — из них выкинут хотя бы $p$. По предположению индукции рекурсия их сортирует. Отсортированная левая часть, $p$, отсортированная правая — отсортированный отрезок, потому что всё слева $\le p<$ всё справа. ∎

Ключевое здесь — опорный элемент выпадает из рекурсии. Именно это гарантирует, что части короче целого, и рекурсия заканчивается.

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

arr = [      |▧|      ]
              p

1. p = arr[0]
2. p = arr[right − 1]
3. p = arr[(left + right) / 2]
4. mediana(arr[0], arr[N/2], arr[N−1])
5. p = arr[random(left, right − 1)]

Медиана трёх — средний по величине из трёх элементов: первого, среднего и последнего.

Индексы в вариантах 1 и 4

Варианты 1 и 4 записаны для всего массива. Qsort работает на подотрезке [left, right), и arr[0] там может вообще не входить в отрезок. Правильно: arr[left] и mediana(arr[left], arr[(left+right)/2], arr[right−1]).

Не из лекции: зачем столько вариантов

От выбора зависит, насколько ровно делится массив, — а от этого асимптотика (раздел 6).

• Крайний элемент (1, 2) — худший выбор на уже отсортированном массиве: опорный оказывается минимумом или максимумом, и одна часть пустая. Отсортированный вход в жизни встречается часто.
• Средний (3) и медиана трёх (4) на отсортированном массиве делят ровно пополам. Но можно специально построить вход, на котором и они дают $O(N^2)$.
• Случайный (5) нельзя подобрать заранее: плохой вход для него не существует, бывают только неудачные случайные выборы. Ожидаемое время — $O(N\log N)$ на любом входе, доказательство в разделе 6.

4. Partition Ломуто

Как работает

Опорный элемент стоит в конце. Массив раскрашен в четыре зоны:

  ≤ p      i    > p      j    необраб.     p
[////////|▢|\\\\\\\\\\|▢|░░░░░░░░░░░░|▧]
 красная      синяя       зелёная      pivot

• i — первый синий, j — первый зелёный;
• [0; i) — элементы ≤ p;
• [i; j) — элементы > p;
• [j; N−1) — элементы необработанные;
• [N−1] — pivot.

Шаг — покрасить первый зелёный элемент arr[j]:

• arr[j] > p → он синий: синяя зона просто растёт, j++;
• arr[j] ≤ p → он красный: swap(arr[i], arr[j]) — первый синий уходит в конец синей зоны, а красный встаёт сразу за красной зоной; i++, j++.

Когда зелёных не осталось, массив выглядит так:

[//////////|▢\\\\\\\\\\\\\\\\\\\\|▧]
            i                     p

Остаётся поменять pivot с первым синим arr[i] — и он встаёт между зонами. $T(N)=O(N)$.

Алгоритм

Partition(arr, left, right)
    p = arr[right − 1]          // иной выбор → swap
    i = left
    for j = left ... right − 2
        если arr[j] ≤ p
            swap(arr[i], arr[j])
            i++
    swap(arr[right − 1], arr[i])
    return i                    // pivot

«Иной выбор → swap» на полях: если опорный выбран не последним элементом (раздел 3), его сначала меняют с arr[right − 1], а дальше алгоритм тот же.

Не из лекции: доказательство через инвариант

Инвариант перед каждой итерацией (с left вместо 0): arr[left … i) $\le p$, arr[i … j) $>p$, arr[right−1] = p.

• Вначале $i=j=left$, обе зоны пустые — верно.
• Шаг, arr[j] > p: j++ добавляет его в синюю зону — верно.
• Шаг, arr[j] ≤ p: если синяя зона непуста, arr[i] — синий ($>p$). После обмена на месте i красный, на месте j синий; i++, j++ сдвигают обе границы — верно. Если синяя зона пуста ($i=j$), обмен элемента с самим собой ничего не меняет, и он просто присоединяется к красной.
• В конце $j=right-1$: всё до i красное, [i, right−1) синее. Обмен arr[i] с pivot ставит $p$ на i. Синий элемент уезжает в конец — он по-прежнему справа и $>p$. Если синих нет, $i=right-1$, обмен с самим собой.

Время: цикл делает ровно $\ell -1$ итераций по $O(1)$ — $\Theta (\ell )$ на любом входе длины $\ell$.

5. Partition Хоара

Считаем на [left, right). Два указателя идут навстречу друг другу:

Partition(arr, left, right)
    p = arr[(left + right) / 2]
    L = left
    R = right − 1
    while (true)
        пока arr[L] < p
            L++
        пока arr[R] > p
            R--
        если L ≥ R
            return R
        swap(arr[L], arr[R])
        L++
        R--

 L →           ← R
[ |≥p|   |p|  |≤p| ]
    └─── swap ───┘
          ⇓
[    ≤    |p|    ≥    ]

L останавливается на элементе ≥ p, R — на элементе ≤ p. Оба стоят не на своих сторонах, и их меняют местами. $T(N)=O(N)$.

С Qsort из раздела 2 эта схема сортирует неправильно

Хоар делит массив иначе, чем Ломуто: после него [left, R] $\le p$ и [R+1, right) $\ge p$, но опорный элемент не обязательно стоит на позиции R. Qsort из раздела 2 выкидывает arr[id_p] из рекурсии как «уже стоящий на месте» — и этот элемент остаётся неотсортированным.

Проверено на C++: на 20 000 случайных массивах длины 1–9 результат неверен в 4548 случаях. Например, 4 3 1 2 3 2 3 3 1 → 1 2 1 3 3 2 3 3 4.

Просто включить R в левую часть — Qsort(left, R + 1), Qsort(R + 1, right) — тоже мало. При p = arr[(left + right) / 2] на полуинтервале средний индекс округляется вверх, и Partition может вернуть R = right − 1. Тогда левая часть совпадает со всем отрезком, и рекурсия бесконечна. Пример: [1, 2]: p = 2, L останавливается на 2, R тоже, возвращается R = 1 = right − 1.

Не из лекции: рабочий вариант Хоара

Partition(arr, left, right)
    p = arr[(left + right − 1) / 2]     // середина с округлением вниз
    ... дальше как на доске, return R
 
Qsort(arr, left, right)
    если right − left ≤ 1
        return
    R = Partition(arr, left, right)
    Qsort(arr, left, R + 1)
    Qsort(arr, R + 1, right)

Проверено на 200 000 случайных массивах длины 1–12 (в том числе с множеством повторов) — ошибок 0, выход за границы под AddressSanitizer не найден.

Почему работает (набросок). Указатели не выходят за отрезок: на первом проходе их останавливает сам $p$, а после обмена слева от L лежит элемент $\le p$, справа от R — элемент $\ge p$, и они служат «барьерами». Все пройденные L элементы $\le p$, все пройденные R элементы $\ge p$ — отсюда разбиение [left, R] / [R+1, right). С округлением середины вниз R на первом проходе останавливается не правее $p$, а дальше только уменьшается, поэтому $R<right-1$ и обе части непустые.

Не из лекции: Хоар против Ломуто

• Ломуто проще доказывать и ставит опорный элемент на место.
• Хоар делает заметно меньше обменов: на $10^5$ случайных числах — 386 114 против 1 037 910 у Ломуто, в 2,7 раза меньше.
• Главное различие — равные элементы. На массиве из одинаковых чисел Ломуто с ≤ отправляет всё влево, разбиение вырождается, и сортировка работает за $O(N^2)$. Хоар останавливается на равных с обеих сторон и делит пополам. Проверено на $N=4000$ одинаковых элементов: Ломуто — 7 998 000 сравнений ($\approx N^2/2$), Хоар — 55 454.

6. Асимптотика

Partition → $T(N)=O(N)$. Рекурсия → $\log N$ уровней.

$T(N)=O(N\log N)$

Примечание: когда разбиение примерно посередине.

        [     |▧|     ]
   partition ↙     ↘
     [     ]         [     ]

Ситуация: опорный элемент — крайний:

[▧|                 ]       ┐
 ▧   [▧|           ]        │
      ▧   [▧|     ]         │ O(N) уровней
           ▧   [▧| ]        │
                            ┘

Получается $T(N)=O(N^2)$.

Не из лекции: почему $N\log N$ и почему $N^2$

Хорошее разбиение. Как в [[Сортировка слиянием|сортировке слиянием]]: на одном уровне рекурсии отрезки не пересекаются, сумма их длин $\le N$, Partition стоит линейно — уровень обходится в $O(N)$. При делении пополам уровней $\lceil {\log }_{2}N\rceil$. Итого $O(N\log N)$. Хватает и неровного деления: если каждая часть не больше $\frac{9}{10}$ целого, уровней ${\log }_{10/9}N=O(\log N)$.

Худший случай. Если опорный — минимум или максимум отрезка, одна часть пустая, другая длины $\ell -1$. Partition стоит $\ell -1$ сравнений: $(N-1)+(N-2)+\dots +1=\frac{N(N-1)}{2}=\Theta (N^2).$ Ломуто с p = arr[right − 1] на отсортированном массиве попадает ровно сюда. Проверено: $N=4000$ — 7 998 000 сравнений, и это ровно $N(N-1)/2$. Глубина рекурсии при этом $N$ — отсюда $M(N)=O(N)$ в худшем случае.

Не из лекции: случайный опорный — $O(N\log N)$ в среднем

Пусть опорный выбирается случайно (вариант 5), элементы разные. Обозначим $z_1<z_2<\dots <z_N$ — элементы в отсортированном порядке.

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

Когда $z_i$ и $z_j$ ($i<j$) сравниваются? Пока опорными выбираются элементы вне $\{z_i,\dots ,z_j\}$, вся эта группа идёт в одну часть вместе. Первый опорный из группы решает: если это $z_i$ или $z_j$, они сравниваются; если любой между ними — $z_i$ и $z_j$ разъезжаются по разным частям и не встретятся никогда. Все $j-i+1$ элементов группы равновероятны, поэтому $P(z_i\text{ и }{z}_j\text{ сравнивались})=\frac{2}{j-i+1}.$

Ожидаемое число сравнений — сумма вероятностей по всем парам: $E={\sum }_{i<j}\frac{2}{j-i+1}\le {\sum }_{i=1}^N{\sum }_{d=2}^N\frac{2}{d}\le 2N\cdot H_N=O(N\log N),$ где $H_N=1+\frac{1}{2}+\dots +\frac{1}{N}\le \ln N+1$ — гармонический ряд. ∎

Проверка: на $10^5$ случайных числах Ломуто сделал 2 091 657 сравнений при оценке $2N\ln N\approx 2302585$.

7. Counting Sort — сортировка подсчётом

• быстрая;
• значения $\in \{0,1,2,3,4\}$, в общем случае $0,1,\dots ,K$, где $K=\max (arr)$.

arr = [ ... ]
count = [0 ... 0]               // K + 1
for i = 0 ... N
    count[arr[i]]++
for i = 0 ... K
    while count[i] > 0
        print(i)
        count[i]--

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

Асимптотика: $T(N)=O(N+K)$.

Нюанс: $K$ маленькое. Неустойчивая.

Не из лекции

• Почему $N+K$. Первый цикл — $N$ шагов. Во втором внешний цикл проходит $K+1$ значений, а все итерации while вместе печатают ровно $N$ чисел. Итого $O(N+K)$, память — $O(K)$ на count.
• Почему $K$ должно быть маленьким. При $K\gg N$ доминирует $K$: для $N=10$ чисел до $10^9$ понадобится массив на миллиард счётчиков. Отрицательные значения тоже не поместятся без сдвига на минимум.
• «Неустойчивая». Эта версия не переставляет исходные элементы, а печатает значения заново. Для голых чисел устойчивость не имеет смысла — равные неотличимы. Но если сортировать записи по ключу, отдельные записи этот алгоритм просто потеряет. Для записей нужна версия из раздела 8.
• Как она обходит нижнюю оценку. Элементы ни разу не сравниваются друг с другом: значение служит индексом в count. Теорема из раздела 9 про сортировки сравнением, и на подсчёт она не распространяется.

8. Устойчивая Counting Sort

arr = [ ... ]                   // N
count = [0 ... 0]               // K + 1
result = [ ... ]                // N
for i = 0 ... N
    count[arr[i]]++
for i = 1 ... K
    count[i] += count[i − 1]
for j = N − 1 ... 0
    result[count[arr[j]] − 1] = arr[i]
    count[arr[j]]--

$T(N)=O(N)$, $M(N)=O(N)$. Устойчивая!!!

Пример на доске — count для значений 0…4:

 0   1   2   3   4
[5 | 7 | 9 | 1 | 5]
 ↓   ↓   ↓   ↓   ↓
 5  13  22  23  28

После префиксных сумм count[v] — сколько элементов $\le v$, то есть номер позиции сразу за последним местом для значения $v$ в отсортированном массиве.

Опечатка и арифметика на доске

• result[count[arr[j]] − 1] = arr[i] — в цикле по j переменной i нет, должно быть = arr[j].
• Префиксные суммы 5 7 9 1 5 — это 5 12 21 22 27: на доске $5+7=13$, и ошибка тянется дальше.
• $T(N)=O(N)$ и $M(N)=O(N)$ верны только при $K=O(N)$. Второй цикл идёт по $K$ значениям, count занимает $K+1$ ячеек: честно $T=O(N+K)$, $M=O(N+K)$.

Не из лекции: почему это сортирует и почему устойчиво

После второго цикла count[v] = число элементов $\le v$. В отсортированном массиве значения $v$ должны занять позиции [count[v−1], count[v]) — после всех меньших.

Третий цикл идёт с конца. Первым из элементов со значением $v$ он встретит самый правый и поставит его на count[v] − 1 — последнее место блока. Затем count[v]--, и следующий (левее в исходном) встанет на место левее. Внутри блока элементы оказываются в исходном порядке — это и есть устойчивость. Если идти с начала, порядок равных развернётся.

Проверка на [2, 0, 1, 2, 0] даёт 0 0 1 2 2. С записями вместо чисел эта версия переносит сами записи, а не печатает значения — поэтому годится как шаг поразрядной сортировки.

9. Теорема (б/д)

Никакая сортировка сравнением не работает быстрее $\Omega (N\log N)$.

На лекции — без доказательства, как и в L04. Доказательство через дерево решений — в Сортировка. Быстрая сортировка и сортировка слиянием — сортировки сравнением, подсчёт — нет (раздел 7).

10. Сортировка за O(1). Камушки!

На доске — горизонтальная линия с камнями разного размера, под ней стрелка «100 м» вниз ко второй линии. Пояснений не записано.

Смысл не записан

Что именно рассказывалось, по конспекту не восстановить. Похоже на шуточный пример «физической» сортировки: камни сбрасывают с высоты и смотрят, в каком порядке они упадут. Если вспомните — допишите.

Грабли

• Хоар + схема Qsort для Ломуто = неверная сортировка. Хоар не ставит опорный на возвращённую позицию, его нельзя выкидывать из рекурсии.
• arr[(left + right) / 2] в Хоаре на полуинтервале — бесконечная рекурсия на [1, 2]. Середину округлять вниз: (left + right − 1) / 2.
• Крайний элемент как опорный на отсортированном массиве — $O(N^2)$.
• Ломуто на одинаковых элементах — тоже $O(N^2)$.
• arr[0] вместо arr[left] при выборе опорного в подотрезке.
• $M(N)=O(1)$ у быстрой сортировки — без учёта стека. Стек — $O(\log N)$ в среднем, $O(N)$ в худшем.
• Сортировка подсчётом при большом $K$ — массив count на $K+1$ ячеек.
• Устойчивый подсчёт с начала массива разворачивает порядок равных. Идти нужно с конца.

После этой лекции должно получаться

• объяснить, что делает Partition и почему опорный элемент не участвует в рекурсии (для Ломуто);
• написать Partition Ломуто и доказать его через четыре зоны;
• объяснить, чем Хоар отличается от Ломуто и почему с ним другая рекурсия;
• показать вход, на котором быстрая сортировка работает за $O(N^2)$, и объяснить, как от этого спасает случайный опорный;
• вывести $O(N\log N)$ для разбиения пополам;
• написать сортировку подсчётом и сказать, когда она выгоднее $N\log N$;
• объяснить, почему устойчивый подсчёт идёт с конца массива;
• объяснить, почему подсчёт не противоречит нижней оценке.