Сортировка подсчетом - это алгоритм сортировки массива данных, где используется диапазон значений массива для подсчета их количества.
История возникновения сортировки подсчетом
Данный алгоритм был предложен в статье "The Distribution Sort" в 1954 году Гарольдом Сьюэллом.
Сортировка подсчетом основана на идее, что если знать, сколько раз встречается каждое значение в массиве, то можно легко определить, на какой позиции должен стоять каждый элемент после сортировки. Для этого создается вспомогательный массив, в котором хранятся частоты встречаемости каждого значения. Затем этот массив используется для заполнения отсортированного массива в соответствии с порядком значений.
Позже данный алгоритм был улучшен Дональдом Кнутом.
Сложность сортировки подсчетом
Сложность сортировки подсчетом считается как O(n+k) по времени и O(k) по пространству, где n - количество элементов массива, а k - размер диапазона выборки массива.
Из данного графика видно, что по времени и пространству сложность сортировки подсчетом линейна, что намного лучше, чем сложность алгоритмов сортировки вставками и пузырьком.
Алгоритм сортировки подсчетом
Для начала загружается массив данных из него мы узнаем его длину n. После узнаем минимальный и максимальный элементы массива и их основе рассчитываем диапазон значений массива k. Затем создается новый массив заполненный 0 длиной k. Подсчитываем количество каждого элемента в исходном массиве, записываем элементы в отсортированном порядке в исходный массив и после выводим массив на печать.
Ручной пример работы сортировки подсчетом
На рисунке выше представлен ручной просчет сортировки подсчетом. Сложность данного примера составила O(38).
Достоинства и недостатки сортировки подсчетом
Достоинства:
- Линейная сложность в среднем и худшем случае, то есть O(n + k), где n - размер массива, а k - диапазон чисел.
- Простота реализации и понимания.
- Не требует сравнения элементов, что может быть полезно для сортировки объектов с дорогой операцией сравнения.
Недостатки:
- Требует дополнительной памяти для хранения вспомогательного массива размера k, что может быть проблематично, если k слишком велико или неизвестно заранее.
- Не может сортировать данные, которые не являются целыми числами или не имеют естественного порядка, например, строки, дроби, структуры и т.д.
- Не является устойчивым, то есть может нарушить относительный порядок равных элементов, что может быть важно для некоторых приложений.