Сортировка подсчетом (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:

  1. HackerEarth: CountingSort (Подсказка: используйте приведенный выше код, измените вывод)

Проблема имеет очень небольшой ввод, поэтому наш предыдущий размер массива переборщил с проблемой. Все, что нам нужно сделать здесь, это настроить размер массива и вместо этого распечатать индекс и значение нашего массива в этом индексе.

2) HackerEarth: ShilandBirthdaypresent (Подсказка: используйте CS, чтобы подсчитать количество отдельных элементов перед определенным числом)

3) HackerEarth: FindingPairs (Подсказка: внедрите US с помощью std :: map)

Поскольку в этой задаче есть отрицательное целое число, мы не можем использовать вектор для хранения значений отрицательных индексов. Использование карты поможет вам пройти все тесты менее чем за 0,5 секунды.