Где применяется
1. Задача
Все сортировки, которые ты видел до сих пор, сравнивают пары. Они спрашивают, больше ли одно число другого, и по ответу решают: поменять местами или идти дальше. Любая сортировка сравнением построена на этом вопросе, и именно из-за него она не может работать быстрее, чем примерно за n log n.
Теперь другая ситуация. Чисел много, но все они целые и из небольшого диапазона. Возраст от 0 до примерно 120. Оценка в звёздах от 1 до 5. Баллы за тест от 0 до 100. Когда значения лежат в таком узком диапазоне, сортировать можно вообще без сравнений.
У тебя 100 000 ответов на опрос, и в каждом оценка от 1 до 5 звёзд. Ты хочешь упорядочить ответы от 1 звезды до 5. Сравнивать ответы между собой незачем: различных значений всего 5.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитcountingSort([3, 1, 4, 1, 0, 3, 2], 4)Все ключи лежат от 0 до 4, поэтому заводим 5 счётчиков, по одному на каждый возможный ключ.
Одна операция: одно сравнение, одно чтение или одна запись. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.
O(n + k)O(n log n)
Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.
Как узнать
Эти слова в условии значат этот паттерн
- ключи это целые числа в небольшом известном диапазоне
- сортировка возрастов, оценок или ограниченных счётчиков
- нужна 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
Задачи с целыми значениями из маленького диапазона, например рост до 100 или число цитирований, ограниченное n. Посчитай каждое значение и выпиши значения по порядку, ничего не сравнивая.
Рост от 1 до 100, поэтому таблица из 101 счётчика даёт отсортированный порядок для сравнения.
Значения не больше 1000, поэтому посчитай их, выпиши сначала значения из arr2, затем остальные по возрастанию.
Возможных значений три, значит три счётчика и одна перезапись массива.
Ограничь каждое число цитирований значением n, посчитай их и иди по таблице вниз от n.