Сигнал задачи
Когда применять
Когда нужно выбрать сортировку под ограничения на память, стабильность и диапазон ключей, а не просто вызвать библиотечную функцию.
Как выбрать подход
- Bubble и selection уместны прежде всего для разбора инвариантов и очень малых входов; selection делает лишь O(n) обменов, а bubble с флагом умеет рано остановиться.
- Heap sort даёт гарантированное O(n log n) и O(1) дополнительной памяти, но не сохраняет порядок равных элементов.
- Counting sort выбирают для целых ключей из небольшого известного диапазона; стабильный вариант позволяет сортировать записи по ключу.
- Radix sort обрабатывает ключи по разрядам и требует стабильной сортировки каждого разряда; выгоден, когда число разрядов и основание контролируемы.
Сложность
- Bubble: O(n²) в среднем и худшем случае, O(n) в лучшем с ранней остановкой; память O(1). Selection: всегда O(n²), память O(1).
- Heap sort: построение кучи O(n), вся сортировка O(n log n), дополнительная память O(1).
- Counting sort: O(n + k) времени; для подсчёта только значений достаточно O(k) дополнительной памяти, а стабильный вариант для записей требует O(n + k) памяти на выход и частоты, где k — размер диапазона ключей.
- Radix sort: O(d · (n + b)) времени и O(n + b) памяти для d разрядов и основания b.
Границы и ошибки
- Counting sort становится непрактичным, если диапазон ключей намного больше входа или его границы заранее неизвестны.
- Нестабильная сортировка разряда нарушает корректность radix sort.
- Heap sort и selection sort нестабильны без дополнительных приёмов; это важно для записей с равными ключами.
- Оценка radix sort не означает безусловное O(n): число разрядов зависит от представления и диапазона ключей.