Рассмотрим этот массив. Что вы замечаете в первую очередь? Да, верно. Этот массив имеет повторяющиеся значения в небольшом диапазоне. Счетный массив использует идею хранения частот элементов. Это сортировка без сравнения. Он не сравнивает свои элементы друг с другом. Посмотрим, как пойдет!
мышление
Что мы можем использовать для хранения частот? Карта? да, мы можем использовать карту. Но мы будем использовать массив. Вы можете спросить, почему? В картах используются функции хеширования. Эти функции используются для преобразования ключа в значение. Это дорого с точки зрения времени и места. Принимая во внимание, что если мы рассматриваем индексы массива, представляющие элементы, и значение этих индексов как частоту этих элементов, мы можем выполнить работу за меньшее пространство и время. Запутались? Посмотрим на картинке ниже-
Глядя на это, вы можете подумать, что хранение на основе карт выглядит менее затратным, но это не так. В первом случае ключи занимают дополнительное место, а во втором случае индексы — это просто адреса. Этот подход полезен только тогда, когда элементы равномерно распределены в диапазоне. Если элементы разрежены, большая часть массива останется неиспользованной. Теперь мы разобрались с использованием массива. Частота сохраняется. После этого мы можем пойти с одним простым и одним хитрым подходом. Первый — неофициальный, который я использовал.
Простая идея
В частотном массиве индексы идут в порядке возрастания. По его подсчету мы можем перейти к каждому индексу и добавить текущий элемент в наш результирующий массив. Посмотрим,
Результирующий массив пуст, а итератор i указывает на 0, следующую свободную позицию. Переходим к массиву счетчиков/частот. Найдите первое значение, счетчик которого не равен нулю, здесь он равен 0. Счетчик нулей равен 1, поэтому он будет вставлен 1 раз, и I будет соответственно увеличен.
Точно так же 1 будет вставлено 3 раза.
В массиве count следующий индекс равен 2, но имеет нулевое значение, поэтому не будет вставлен. Мы будем двигаться вперед, и процесс будет продолжаться!
Псевдокод
Можно подумать, что есть два вложенных цикла, поэтому сложность будет квадратичной, но здесь это не так. Внутренний цикл всегда выполняется столько раз, сколько раз элемент присутствует в массиве. Временная сложность — это количество сделанных сравнений. Здесь, если вы внимательно посмотрите, весь процесс был выполнен только столько раз, сколько раз присутствовал элемент. Если элемент отсутствует, он не входит во второй цикл. Таким образом, временная сложность является линейной или O (N).
Фактический алгоритм
Это формальный алгоритм сортировки подсчетом. После получения массива частот мы не будем хранить кумулятивную частоту. Каждый индекс будет хранить сумму частот до сих пор. На картинке вы заметите, что выделенные частоты на самом деле являются позициями, где вводится новое число и изменяется совокупная частота.
Идем дальше по алгоритму. Для каждого элемента X во входном массиве
- Перейти к тому же индексу X и уменьшить значение в массиве частот
- Рассматривайте уменьшенное значение как позицию X в массиве результатов, скажем, это значение i.
- Поместите X в массив результатов на i-ю позицию.
Сначала давайте посмотрим картинки, а потом я расскажу вам, почему это работает.
В первой итерации — для 9 во входном массиве мы переходим к индексу 9 в массиве частот. Уменьшите его значение с 10 до 9. Затем перейдите на 9-ю позицию в массиве результатов.
Для 5 мы переходим на 5-ю позицию в массиве частот, уменьшаем его значение с 7 до 6. Затем переходим на 6-ю позицию в массиве результатов.
Таким же образом происходит процесс.
Псевдокод
Почему это работает?
Если мы внимательно посмотрим, количество каждого элемента X в кумулятивном массиве частот представляет собой количество элементов в отсортированном массиве результатов до X (включительно). Другими словами, мы можем сказать, что количество X показывает позицию X в массиве результатов, а индекс равен позиции-1; поэтому мы уменьшаем. Например, значение 3 равно 5, это говорит нам о том, что 3 находится на 5-й позиции в результирующем массиве, что видно, когда мы смотрим на окончательный отсортированный массив. Надеюсь, ты это понял.
Сложность времени и пространства
Есть три цикла, но ни один из них не является вложенным. Таким образом, временная сложность является линейной или O (R), что означает, что время, необходимое для запуска этого процесса, будет пропорционально диапазону чисел. Вот почему нам нужен небольшой диапазон чисел, которые равномерно распределены, чтобы этот алгоритм работал эффективно. Говоря о пространственной сложности, этот термин означает дополнительное пространство, необходимое для запуска алгоритма. Это также O(R), так как нам нужен массив, равный диапазону, для хранения частот. Это общий обзор алгоритма. Надеюсь, вам понравилась статья.
Счастливого обучения!
