Алгоритм сортировки подсчетом (Counting Sort): принцип работы

Идея метода сортировки

Существует математически доказанная теорема: любой алгоритм сортировки, основанный на сравнениях, не может работать быстрее, чем за O(N log N) в худшем случае. Это фундаментальное ограничение.

Но что, если не сравнивать элементы вообще? Сортировка подсчетом обходит это ограничение, используя сами сортируемые значения как индексы вспомогательного массива.

Алгоритм работы

• Шаг 1. Создаем вспомогательный массив count размером K (где K - максимальное возможное значение элемента), заполняем его нулями.
• Шаг 2. Проходим по исходному массиву. Встретив число x, увеличиваем count[x] на единицу.
• Шаг 3. Проходим по массиву count слева направо. Если count[x] = 3, мы записываем число x три раза подряд в исходный массив, двигая указатель.

На схеме ниже можно посмотреть, как сортировка подсчетом находит правильные позиции чисел вообще без сравнений - только за счет счетчиков.

Ограничения алгоритма

Сортировка подсчетом кажется идеальной (линейное время!), но у нее есть строгие ограничения:

• Требует памяти O(K): Если нужно отсортировать массив из пяти чисел [1, 1000000, 5, 2, 8], нам придется создать вспомогательный массив размером в миллион элементов! Алгоритм эффективен, только когда K сопоставимо с N.
• Только целые неотрицательные числа: Алгоритм напрямую использует значения как индексы массива, поэтому он не работает с дробными числами (float). Отрицательные числа можно поддержать, найдя минимум и сделав сдвиг на это значение, но это требует дополнительных операций.

Реализация на C

// Функция сортировки подсчетом. 
// k - максимальное значение в массиве (диапазон [0..k])
void CountingSort(int arr[], int n, int k) {
    // Выделяем память под массив счетчиков, инициализируем нулями
    int* count = (int*)calloc(k + 1, sizeof(int));
    
    // Шаг 1: Подсчет частоты каждого элемента
    for (int i = 0; i < n; i++) {
        count[arr[i]]++;
    }
    
    // Шаг 2: Восстановление отсортированного массива
    int index = 0;
    for (int i = 0; i <= k; i++) {
        while (count[i] > 0) {
            arr[index] = i;
            index++;
            count[i]--;
        }
    }
    
    free(count); // Освобождаем память
}