Сортировка подсчетом (CS)
Представляем:
Одним из наиболее эффективных алгоритмов сортировки является быстрая сортировка, время выполнения которой равно O (n * log (n)), и вы когда-нибудь задумывались, есть ли какие-нибудь альтернативы, которые могут побить эту скорость? В общем, это не совсем осуществимо. Однако, если входные данные и требования задачи имеют особые свойства, доступен еще более эффективный алгоритм - сортировка с подсчетом (CS). CS, который также известен как «Lùa bò vào chuồng» или «Đếm phân phối» на вьетнамском языке, действительно легко реализуемый и не основанный на сравнении алгоритм. Этот алгоритм работает с линейным временем и действительно подходит для задачи, имеющей небольшое количество отдельных элементов, таких как целые числа в определенном диапазоне.
Идея CS:
Основная идея реализации CS очень проста. Он работает путем подсчета количества объектов, имеющих различные значения ключей, а затем мы можем использовать эти данные для решения различных проблем.
Чтобы глубже понять CS, давайте взглянем на основную проблему этого алгоритма:
Вам дан целочисленный массив A размера N. Каждый элемент массива находится в диапазоне от 1 до 1⁰⁵. Отсортируйте массив по возрастанию.
Ограничения:
1≤N≤100
Пример ввода:
12
1 4 2 7 8 2 1 3 8 6 2 4
Пример вывода:
1 1 2 2 2 3 4 4 6 7 8 8
Новичок в реализации:
Сначала мы инициируем целочисленный массив из 100000 элементов, поскольку ограничение a [i] составляет от 1 до 1⁰⁵. Затем прочитайте ввод и увеличьте значение нашего массива на единицу по индексу целого числа из вывода с линейным временем (O (n)). Наконец, пройдемся по нашему целочисленному массиву, проверяем по каждому индексу i, если значение все еще больше нуля, выведите число i, уменьшите значение на единицу и повторите процесс проверки.
Код C ++:
Общая сложность: O (n + k), k - целочисленный диапазон.
Оптимизированный код:
Мы можем оптимизировать код, игнорируя числа, которых нет в выводе. Это легко сделать с помощью std :: set в C ++, поскольку он не позволяет использовать избыточный ключ в одном наборе. Итерации по набору займут только O (размер этого набора).
Общая сложность: O (n + p), p - количество различных элементов.
Практика задач в CS:
- HackerEarth: CountingSort (Подсказка: используйте приведенный выше код, измените вывод)
Проблема имеет очень небольшой ввод, поэтому наш предыдущий размер массива переборщил с проблемой. Все, что нам нужно сделать здесь, это настроить размер массива и вместо этого распечатать индекс и значение нашего массива в этом индексе.
2) HackerEarth: ShilandBirthdaypresent (Подсказка: используйте CS, чтобы подсчитать количество отдельных элементов перед определенным числом)
3) HackerEarth: FindingPairs (Подсказка: внедрите US с помощью std :: map)
Поскольку в этой задаче есть отрицательное целое число, мы не можем использовать вектор для хранения значений отрицательных индексов. Использование карты поможет вам пройти все тесты менее чем за 0,5 секунды.