Сортировка

Сортировка (sorting) переставляет элементы массива так, чтобы они шли по порядку. Набор элементов не меняется — меняется только их расположение.

Зачем нужно

На лекции названы применения: фильтры, маркетплейсы, бинарный поиск. Бинарный поиск вообще работает только на отсортированном массиве.

Как работает

Определение

Было $a_0,a_1,\dots ,a_N$ — стало $a_{(0)},a_{(1)},\dots ,a_{(N)}$, и

$\{a_0,a_1,\dots ,a_N\}=\{a_{(0)},a_{(1)},\dots ,a_{(N)}\}.$

Виды порядка:

возрастание	$a_{(0)}<a_{(1)}<\cdots <a_{(N)}$
неубывание	$a_{(0)}\le a_{(1)}\le \cdots \le a_{(N)}$
убывание	$a_{(0)}>a_{(1)}>\cdots >a_{(N)}$
невозрастание	$a_{(0)}\ge a_{(1)}\ge \cdots \ge a_{(N)}$

Не из лекции: равные элементы

При повторах строгого возрастания не бывает, поэтому «по возрастанию» на практике значит по неубыванию.

Свойства

Сортировки сравнивают по трём свойствам:

• время выполнения $T(N)$;
• дополнительная память $M(N)$ — см. Время работы алгоритма;
• устойчивость (стабильность, stability) — сохраняется ли порядок одинаковых элементов.

устойчивая:     [1̇, 2, 1̈] → [1̇, 1̈, 2]
неустойчивая:   [1̇, 2, 1̈] → [1̈, 1̇, 2]

Не из лекции: когда устойчивость важна

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

Алгоритмы курса

Алгоритм	$T(N)$	$M(N)$	Устойчива
тривиальный (перемешать и проверить)	$O(N\cdot N!)$
выбором	$O(N^2)$	$O(1)$	нет
вставками	$O(N^2)$	$O(1)$	да
пузырьком	$O(N^2)$	$O(1)$	да

Не из лекции: тривиальный алгоритм

Перемешать стоит $O(N)$, а не $O(1)$, как на доске, — на итог это не влияет. Оценка $O(N\cdot N!)$ — среднее: в среднем нужно $N!$ попыток, но гарантированного времени нет. Подробно — в конспекте L03.

Тонкости

• Одинаковая оценка не значит одинаковое поведение: выбор делает $\Theta (N^2)$ сравнений на любом входе, вставки на уже отсортированном массиве — $O(N)$. См. Квадратичные сортировки.
• Устойчивость обычно решается одним знаком: где строгое сравнение, а где нестрогое.

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

• Путать «отсортировать» с «переупорядочить как угодно»: элементы обязаны остаться те же, без потерь и дублей.
• Считать устойчивость свойством результата. Отсортированный массив чисел выглядит одинаково — устойчивость видна только на записях с ключами.

Углубление — АиСД L04

Быстрее квадрата

Сортировка слиянием: $T(N)=O(N\log N)$, $M(N)=O(N)$, устойчива.

Алгоритм	$T(N)$	$M(N)$	Устойчива
выбором, вставками, пузырьком	$O(N^2)$	$O(1)$	выбор — нет, остальные — да
слиянием	$O(N\log N)$	$O(N)$	да

При $N=10^6$ квадратичная сортировка — около $10^4$ секунд, сортировка за $N\log N$ — около 0,2 секунды. За скорость платят памятью.

Нижняя оценка

Теорема (о сортировках сравнением). Никакая сортировка сравнением не работает быстрее $\Omega (N\log N)$. На лекции — без доказательства.

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

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

Нарисуем её работу на массиве из N разных элементов как двоичное дерево. Узел — сравнение, две ветки — два исхода, лист — конец работы. Каждый вход проходит по дереву путь от корня к листу.

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

Порядков $N!$, значит, листьев не меньше $N!$. У двоичного дерева высоты $h$ не больше $2^h$ листьев: $2^h\ge N!$, $h\ge {\log }_{2}N!$.

Оценка ${\log }_{2}N!$. Из множителей $1,2,\dots ,N$ хотя бы $N/2$ не меньше $N/2$, поэтому $N!\ge (N/2{)}^{N/2}$ и

$h\ge {\log }_{2}N!\ge \frac{N}{2}{\log }_2\frac{N}{2}=\Omega (N\log N).$

Высота дерева — число сравнений на худшем входе. ∎

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

Следствие: Сортировка слиянием с её $O(N\log N)$ асимптотически лучше сделать нельзя.

Углубление — АиСД L05

Алгоритм	$T(N)$	$M(N)$	Устойчива
слиянием	$O(N\log N)$	$O(N)$	да
быстрая	$O(N\log N)$ в среднем, $O(N^2)$ в худшем	$O(\log N)$ на стек	нет
подсчётом	$O(N+K)$	$O(N+K)$	устойчивая версия — да

На доске у быстрой сортировки $M(N)=O(1)$, а у подсчёта $T=M=O(N)$. В таблице — уточнённые оценки, разбор в конспекте L05.

Разные сортировки → разные константы. Слиянием и быстрая — обе $O(N\log N)$, но быстрая не копирует элементы в буфер и обычно быстрее.

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

Теорема о нижней оценке повторена на L05 без доказательства. Сортировка подсчётом её не нарушает: она не сравнивает элементы, а использует значение как индекс массива счётчиков. Поэтому линейное время возможно — но только для небольших целых значений.

Устойчивость у подсчёта — не знак сравнения, как у Merge, а направление прохода: устойчивая версия раскладывает элементы с конца массива.