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

Сортировка подсчётом — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива или списка для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Эффективность алгоритма падает, если при попадании нескольких различных элементов в одну ячейку, их надо дополнительно сортировать.

Простой алгоритм

Это простейший вариант алгоритма. Создать вспомогательный массив [math]C[0..k - 1][/math], состоящий из нулей, затем последовательно прочитать элементы входного массива [math]A[/math], для каждого [math]A[i][/math] увеличить [math]C[A[i]][/math] на единицу. Теперь достаточно пройти по массиву [math]C[/math], для каждого [math]j \in \{0, ..., k - 1\}[/math] в массив [math]A[/math] последовательно записать число [math]j[/math] [math] C[j][/math] раз.

SimpleCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    b = 0;
    for j = 0 to k - 1
        for i = 0 to C[j] - 1
            A[b] = j;
            b = b + 1;

Устойчивый алгоритм

В этом варианте помимо входного массива [math]A[/math] потребуется два вспомогательных массива — [math]C[0..k - 1][/math] для счётчика и [math]B[0..n - 1][/math] для отсортированного массива. Сначала следует заполнить массив [math]C[/math] нулями, и для каждого [math]A[i][/math] увеличить [math]C[A[i]][/math] на 1. Далее подсчитывается число элементов меньше или равных текущему. Для этого каждый [math]C[j][/math], начиная с [math]C[1][/math], увеличивают на [math]C[j - 1][/math]. На последнем шаге алгоритма читается входной массив с конца, значение [math]C[A[i]][/math] уменьшается на 1 и в каждый [math]B[C[A[i]]][/math] записывается [math]A[i][/math]. Алгоритм устойчив.

StableCountingSort
    for i = 0 to k - 1
        C[i] = 0;
    for i = 0 to n - 1
        C[A[i]] = C[A[i]] + 1;
    for j = 1 to k - 1
        C[j] = C[j] + C[j - 1];
    for i = n - 1 to 0
        C[A[i]] = C[A[i]] - 1;
        B[C[A[i]]] = A[i];

Обобщение на произвольный целочисленный диапазон

Если диапазон значений (min и max) заранее не известен, можно воспользоваться линейным поиском min и max, что не повлияет на асимптотику алгоритма. При работе с массивом [math]C[/math] из [math]A[i][/math] необходимо вычитать min, а при обратной записи прибавлять.

Анализ

В первом алгоритме первые два цикла работают за [math]\Theta(k)[/math] и [math]\Theta(n)[/math], соответственно; двойной цикл за [math]\Theta(n + k)[/math]. Во втором алгоритме циклы занимают [math]\Theta(k)[/math], [math]\Theta(n)[/math], [math]\Theta(k)[/math] и [math]\Theta(n)[/math], соответственно. Итого оба алгоритма имеют линейную временную трудоёмкость [math]\Theta(n + k)[/math]. Используемая память в первом алгоритме равна [math]\Theta(k)[/math], а во втором [math]\Theta(n + k)[/math].

Ссылки

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