Где применяется
1. Задача
Сортировка подсчётом из прошлого урока работает быстро, но у неё есть слабое место. Она заводит по счётчику на каждое возможное значение, от 0 до самого большого числа. Для чисел до 9 это 10 ячеек, и всё хорошо. Для номеров (id) до миллиарда это миллиард ячеек. Столько памяти у программы обычно нет.
При этом цифр у таких номеров мало. У числа до миллиарда не больше 10 цифр. Отсюда вопрос: можно ли сортировать, глядя каждый раз на одну цифру, а не на всё число сразу?
У тебя 200 000 номеров заказов, каждый не больше 9 999 999. Их нужно отсортировать, и быстро. Массив из десяти миллионов счётчиков заводить не хочется.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитКак узнать
Эти слова в условии значат этот паттерн
- ключи это целые числа в небольшом известном диапазоне
- сортировка возрастов, оценок или ограниченных счётчиков
- нужна O(n), а сравнения стали узким местом
- сортировка по разрядам или ключу фиксированной ширины
- n большое, но диапазон значений намного меньше n
Похоже, но не то
- Быстрая сортировка (merge / quick) (Fast sort (merge / quick))
Никакая сортировка сравнением не быстрее n log n. Чтение ключа обходит этот предел целиком.
- Хеш-множество / словарь (Hash set / map)
Словарь тоже считает значения, но порядка не хранит. Сортировка подсчётом делает значение индексом.
- Сортировка с пользовательским компаратором (Sort with a custom comparator)
Компаратор описывает порядок между двумя элементами. Подсчёт вообще не смотрит на пары.
- Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion))
Те сравнивают соседей и стоят n в квадрате. Подсчёт линеен, если диапазон позволяет.
n значений с ключами меньше k дают O(n + k). Поразрядная стоит O(d умножить на n) при d разрядах.
На LeetCode
Задачи, где большие целые числа или строки цифр одной длины нужно отсортировать за линейное время, а полная таблица счётчиков слишком велика. Сортируй по одной цифре за проход и сохраняй порядок равных.
Условие требует линейного времени, поэтому отсортируй числа поразрядно и сравни соседей.
Дополнительный вопрос прямо просит поразрядную сортировку, так что сортируй строки цифр начиная с последней цифры.
Прибавь к каждому значению 50000, чтобы не осталось отрицательных, и отсортируй поразрядно.