Сортировка подсчетом

Сортировка подсчетом (Counting Sort) – некомпаративный алгоритм сортировки. В отличие от пузырьковой сортировки или быстрой сортировки (QuickSort), которые сравнивают элементы друг с другом, этот метод использует значения элементов как индексы в дополнительном массиве. Это позволяет достичь линейной временной сложности, если диапазон входных данных невелик.

Как работает сортировка подсчетом

Алгоритм работает в несколько этапов, основываясь на подсчете частоты вхождения каждого элемента во входной массив.

1. Поиск диапазона: Определяется минимальное и максимальное значение, чтобы узнать размер диапазона (k).
2. Создание массива частот: Создается вспомогательный массив count размером k+1, где индекс соответствует значению элемента, а значение ячейки – количеству вхождений этого числа.
3. Накопление суммы: Массив count модифицируется таким образом, чтобы каждая ячейка содержала количество элементов, меньших или равных индексу. Это необходимо для определения точной позиции элемента в результирующем массиве.
4. Формирование результата: Создается результирующий массив. Элементы расставляются на нужные позиции согласно данным из массива частот, после чего счетчик для этого значения декрементируется.

Любые математические вычисления и алгоритмы носят ознакомительный характер. Для критически важных систем используйте проверенные стандартные библиотеки языков программирования.

Выше представлен инструмент для визуализации процесса сортировки подсчетом. Введите массив целых чисел, чтобы увидеть, как значения распределяются по частотному массиву и преобразуются в отсортированный список.

Временная и пространственная сложность

Эффективность алгоритма сильно зависит от характера входных данных:

• Временная сложность: O(n + k), где n – количество элементов, а k – диапазон значений. Это быстрее, чем сортировки сравнением (O(n log n)), когда k не слишком велико.
• Пространственная сложность: O(n + k). Требуется дополнительная память как под массив частот, так и под выходной массив.

Если значения в массиве сильно разбросаны (например, массив из 5 чисел [1, 1000000000, 2, 5, 3]), сортировка подсчетом потребует выделения гигантского массива частот, что делает её непрактичной.

Пример реализации на Python

Для закрепления понимания рассмотрим простую реализацию сортировки подсчетом. Обратите внимание: код предполагает неотрицательные целые числа.

def counting_sort(arr):
    if not arr:
        return arr

    max_val = max(arr)
    min_val = min(arr)
    range_of_elements = max_val - min_val + 1

    count_arr = [0] * range_of_elements
    output_arr = [0] * len(arr)

    # Подсчет вхождений
    for i in range(len(arr)):
        count_arr[arr[i] - min_val] += 1

    # Превращение в накопленную сумму
    for i in range(1, len(count_arr)):
        count_arr[i] += count_arr[i-1]

    # Заполнение выходного массива (идти нужно с конца для стабильности)
    for i in range(len(arr) - 1, -1, -1):
        output_arr[count_arr[arr[i] - min_val] - 1] = arr[i]
        count_arr[arr[i] - min_val] -= 1

    return output_arr

Преимущества и недостатки

Плюсы

• Линейное время выполнения в лучших сценариях.
• Стабильность сортировки (сохраняет порядок одинаковых элементов).
• Простота реализации для ограниченных диапазонов данных.

Минусы

• Высокое потребление памяти при больших k.
• Невозможность использования для чисел с плавающей точкой или строк (без специфических преобразований).
• Неэффективность на разреженных наборах данных.

Сортировку подсчетом целесообразно применять в задачах, где диапазон значений (k) сопоставим с размером массива (n) или меньше его, а также в качестве подпрограммы для других алгоритмов, таких как поразрядная сортировка (Radix Sort).