Сортировка подсчётом (Counting Sort)

Сортировка подсчётом — это алгоритм, который особенно эффективен, когда:

• диапазон значений элементов массива ограничен и известен заранее (например, числа от 0 до 1000);
• данные представлены целыми числами;
• важна линейная скорость работы — O(n + k), где k — диапазон значений.

Идея алгоритма

1. Создаём вспомогательный массив (буфер) длиной k+1, где k — максимальное значение в исходных данных.
2. Проходим по исходному массиву и считаем, сколько раз встречается каждое значение (увеличиваем соответствующую ячейку буфера).
3. Проходим по буферу и распаковываем данные в отсортированный массив.

Таким образом, мы не сравниваем элементы между собой, как в пузырьке или быстрой сортировке, а используем прямой подсчёт.

Теоретические особенности

Сложность: O(n + k).

• n — количество элементов.
• k — диапазон значений.

Ограничения: плохо работает, если диапазон k очень большой по сравнению с n. Например, сортировать 100 чисел в диапазоне до миллиарда — неэффективно.

Стабильность: базовая версия нестабильна, но её можно модифицировать для стабильности (важно, если мы сортируем не только числа, но и связанные с ними объекты).

Применение:

• сортировка оценок школьников (0–100),
• распределение по категориям (например, возраст 0–120),
• задачи в системах с ограниченным диапазоном значений.

Пример 1. Сортировка подсчётом для списка Python

def counting_sort(arr):
    if not arr:
        return arr
    
    # Находим максимальное значение (ограничение диапазона), часто оно известно заранее
    max_val = max(arr)
    
    # Шаг 1: создаём буфер для подсчёта
    count = [0] * (max_val + 1)
    
    # Шаг 2: заполняем буфер (подсчёт элементов)
    for num in arr:
        count[num] += 1
    
    # Шаг 3: распаковываем данные обратно в массив
    sorted_arr = []
    for num, freq in enumerate(count):
        sorted_arr.extend([num] * freq)
    
    return sorted_arr

# Пример использования
data = [1, 3, 7, 2, 10, 2, 7, 1, 1, 7]
print("Оригинальный список:", data)
sorted_data = counting_sort(data)
print("Отсортированный список:", sorted_data)

Пример 2. Сортировка подсчётом с NumPy

import numpy as np

def counting_sort_numpy(arr):
    if arr.size == 0:
        return arr
    
    # Находим максимум
    max_val = arr.max()
    
    # Шаг 1: создаём буфер (используем zeros для быстроты)
    count = np.zeros(max_val + 1, dtype=int)
    
    # Шаг 2: подсчёт элементов
    for num in arr:
        count[num] += 1
    
    # Шаг 3: распаковка (с помощью repeat)
    sorted_arr = np.repeat(np.arange(len(count)), count)
    
    return sorted_arr

# Пример использования
data_np = np.array([1, 3, 7, 2, 10, 2, 7, 1, 1, 7])
print("Оригинальный массив:", data_np)
sorted_np = counting_sort_numpy(data_np)
print("Отсортированный массив:", sorted_np)

Вывод

• Сортировка подсчётом — один из немногих алгоритмов, работающих за O(n).
• Но её использование ограничено диапазоном значений.
• В задачах с небольшим диапазоном целых чисел — это один из самых быстрых способов сортировки.