Как выбрать сортировку под данные

Коротко

Выбор сортировки начинается не с алгоритма, а с ВОПРОСА «что я знаю про данные и что мне нужно». Ключи целые в узком диапазоне - подсчётом или поразрядно (Θ(n)). Данные почти упорядочены - вставками или Timsort (Θ(n)). Нужна устойчивость (многоключевая сортировка) - слияние/Timsort. Память в дефиците, а гарантия важна - пирамидальная (на месте, n·log n). Массив крохотный - вставками. Во всех прочих случаях - встроенная сортировка, она гибрид и уже всё учла. Главный практический совет: почти всегда бери ВСТРОЕННУЮ; свою пиши, только если точно знаешь особенность данных, которую она не использует.

Если ты умеешь выбрать сортировку по свойствам данных (диапазон ключей, упорядоченность, нужна ли устойчивость, память) и знаешь, что по умолчанию берут встроенную, листай до «Теперь сам».

Как думаешь, с чего начинать выбор сортировки

Не с вопроса «какая сортировка самая быстрая» - такой нет, мы это видели весь раздел. Начинать надо с вопроса о ДАННЫХ и ЗАДАЧЕ: какие у меня ключи? упорядочены ли данные? нужна ли устойчивость? сколько есть памяти? насколько велик массив? Ответы на эти вопросы и указывают на сортировку. Сортировка - не универсальный молоток, а набор инструментов, и правильный выбирается по свойствам того, что сортируешь.

На что это похоже

Выбор транспорта. «Какой транспорт самый быстрый?» - вопрос без ответа: смотря куда, сколько груза, какие дороги. В соседний магазин - пешком; через страну - самолёт; с тонной щебня - грузовик. Так и с сортировкой: сперва опиши «маршрут» (свойства данных), потом выбирай «транспорт». Опытный инженер не заучивает «всегда беру X» - он читает условия задачи и достаёт подходящее.

Механизм: дерево вопросов к данным

Пройди по вопросам сверху вниз - первый подошедший ответ и есть выбор.

Ключи - целые в небольшом диапазоне k? (оценки, возрасты, байты) → сортировка ПОДСЧЁТОМ, Θ(n + k). Ключи - целые/строки фиксированной небольшой длины? → ПОРАЗРЯДНАЯ, Θ(d·(n+b)). Это единственный способ обогнать n·log n.
Данные уже почти упорядочены? → ВСТАВКАМИ или Timsort, близко к Θ(n).
Нужна устойчивость (сортировка по нескольким ключам, сохранить порядок равных)? → СЛИЯНИЕ или Timsort (встроенная сортировка объектов).
Память в жёстком дефиците, но гарантия n·log n важна? → ПИРАМИДАЛЬНАЯ (на месте, без худшего случая).
Массив совсем маленький (десятки элементов)? → ВСТАВКАМИ (мало накладных расходов).
Во всех прочих случаях → ВСТРОЕННАЯ сортировка (гибрид: Timsort/introsort). Она уже быстра на практике, защищена от худшего случая и, для объектов, устойчива.

Правило

Сортировку выбирают по свойствам ДАННЫХ и требованиям задачи, а не по привычке: целые в узком диапазоне - подсчётом/поразрядно; почти упорядочены - вставками/Timsort; нужна устойчивость - слияние/Timsort; дефицит памяти + гарантия - пирамидальная; крохотный массив - вставками; иначе - ВСТРОЕННАЯ. По умолчанию бери встроенную; свою пиши, только если знаешь особенность данных, которую встроенная не использует.

Разбор: сводная таблица

Собери весь раздел в одну картину - по чему сортировки различаются и когда какую брать.

сортировка	время (худш.)	память	устойчива	когда брать
вставками	`Θ(n²)`	`O(1)`	да	почти упорядочен; крохотный массив
выбором	`Θ(n²)`	`O(1)`	нет	дорогие обмены (минимум перемещений)
пузырёк	`Θ(n²)`	`O(1)`	да	почти не берут; ранний выход на упорядоченном
Шелла	~`Θ(n^1.5)`	`O(1)`	нет	приличная скорость минимумом кода, без памяти
слиянием	`Θ(n·log n)`	`Θ(n)`	да	нужна устойчивость/гарантия; внешняя сортировка
быстрая	`Θ(n²)`	`Θ(log n)`	нет	общий случай на месте (со страховкой)
пирамидальная	`Θ(n·log n)`	`O(1)`	нет	гарантия `n·log n` при дефиците памяти
подсчётом	`Θ(n + k)`	`Θ(k)`	да	целые в малом диапазоне
поразрядная	`Θ(d(n+b))`	`Θ(n+b)`	да	целые/строки фикс. длины, много данных

Три главных оси выбора: ВРЕМЯ (и гарантия против среднего), ПАМЯТЬ (на месте или буфер), УСТОЙЧИВОСТЬ. Плюс два «читерских» пути мимо n·log n - подсчётом и поразрядно, если позволяют ключи.

Разбор: почему по умолчанию - встроенная

Может показаться, что раз мы всё это изучили, надо писать сортировку под каждую задачу. На практике - наоборот: в 95% случаев правильный ответ «вызови встроенную». Она гибрид (Timsort/introsort), а значит уже: быстра на практике, защищена от Θ(n²), устойчива (для объектов), вылизана и протестирована годами. Самописная сортировка почти наверняка будет медленнее и с багами (вспомни, сколько ловушек у одной быстрой). Знание алгоритмов нужно не чтобы писать их руками, а чтобы: (1) понимать поведение встроенной (устойчива ли? когда Θ(n)?); (2) выбрать НЕ встроенную в тех редких случаях, когда данные позволяют обогнать её (целые в малом диапазоне → подсчёт); (3) не наступать на грабли (не сортировать в цикле то, что можно один раз). Изучать сортировки, чтобы потом брать встроенную, - не парадокс, а зрелость.

Что ломается без этого

Первая ошибка - выбирать сортировку «по привычке» («всегда беру быструю») и упускать: для целых в малом диапазоне подсчёт даёт Θ(n) вместо n·log n; для почти упорядоченных Timsort даёт Θ(n); для многоключевой нужна устойчивость. Вторая - писать свою сортировку там, где встроенная лучше: получишь худший случай и баги. Третья - забыть про требование задачи (устойчивость, память) и выбрать сортировку, которая его нарушает: взял быструю там, где нужна была устойчивость, - и многоключевой порядок сломался. Выбор без вопросов к данным - это выбор наугад.

Зачем это в работе

Этот урок - практический итог всего раздела. В реальной работе ты почти никогда не пишешь сортировку - ты ВЫБИРАЕШЬ: чаще всего встроенную, изредка - подсчёт/поразрядную под особые ключи. Но чтобы выбрать верно, надо задать данным правильные вопросы: диапазон ключей, упорядоченность, нужна ли устойчивость, сколько памяти. Именно это отличает инженера, который понимает свои инструменты, от того, кто знает одно слово «сортировка». А ещё этот навык шире сортировок: «сначала опиши данные и требования, потом выбирай алгоритм» - универсальный способ принимать инженерные решения.

Теперь сам

Тебе надо отсортировать 10 миллионов записей о посетителях по возрасту (возраст 0-120), причём среди ровесников важно сохранить порядок их прихода. Какую сортировку выбрать и почему? Что если бы порядок ровесников был не важен?

Ответ. Ключ - возраст, это целое в МАЛЕНЬКОМ диапазоне (k = 121), а записей очень много - идеальный случай для сортировки ПОДСЧЁТОМ: Θ(n + k) = Θ(n), быстрее любой n·log n. Но есть требование - сохранить порядок ровесников (устойчивость). Значит нужен УСТОЙЧИВЫЙ вариант подсчёта (через префиксные суммы) - он и устойчив, и линеен, оба требования выполнены. Если бы порядок ровесников был НЕ важен, устойчивость не нужна, и годился бы любой вариант подсчёта (или, при нежелании писать своё, встроенная сортировка - но подсчёт здесь всё равно быстрее из-за малого диапазона). Решает профиль данных: малый диапазон целых → подсчёт; нужен порядок равных → устойчивый.

Главное

Сортировку выбирают по свойствам ДАННЫХ и задачи, а не по привычке. Дерево вопросов: целые в узком диапазоне → подсчётом/поразрядно (Θ(n), обгоняет n·log n); почти упорядочены → вставками/Timsort (Θ(n)); нужна устойчивость → слияние/Timsort; дефицит памяти + гарантия → пирамидальная; крохотный массив → вставками; иначе → ВСТРОЕННАЯ (гибрид, уже всё учла). Три оси выбора - время (гарантия vs средний), память (на месте vs буфер), устойчивость. По умолчанию бери встроенную; знание алгоритмов нужно, чтобы понимать её поведение и выбрать иное, когда данные это позволяют.