Участник:Nechaev/Черновик

Сортировка подсчётом — алгоритм сортировки целых чисел в диапазоне от [math]0[/math] до некоторой константы [math]k[/math], работающий за линейное время.

Основная идея

Основная идея сортировки подсчетом заключается в том, чтобы для каждого элемента [math]x[/math] определить количество элементов, которые меньше [math]x[/math]. С помощью этого, мы можем поместить элемент туда, где он должен находиться в отсортированном массиве. Например, если есть [math]42[/math] элемента, которые меньше [math]x[/math], то после сортировки он будет занимать [math]43[/math]-ю позицию. Если допускается, что несколько элементов могут иметь одинаковое значение, то алгоритм придётся модифицировать, потому что мы не можем разместить все такие элементы в одной позиции.

Использование сортировки подсчётом целесообразно, когда диапазон возможных значений входных данных достаточно мал по сравнению с количеством элементов в сортируемом множестве, например, миллион натуральных чисел меньших [math]1000[/math]. Эффективность алгоритма падает, когда необходимо сортировать различные элементы, попавшие в одну ячейку.

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

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

SimpleCountingSort
    for number = 0 to k - 1
        C[number] = 0;
    for i = 0 to length[A] - 1
        C[A[i]] = C[A[i]] + 1;
    pos = 0;
    for number = 0 to k - 1
        for i = 0 to C[j] - 1
            A[pos] = number;
            pos = pos + 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[number][/math], начиная с [math]C[1][/math], увеличивают на [math]C[number - 1][/math]. На последнем шаге алгоритма читается входной массив с конца и в каждый [math]B[C[A[i]]][/math] записывается [math]A[i][/math], а значение [math]C[A[i]][/math] уменьшается на 1. Алгоритм устойчив. Устойчивость может потребоваться при сортировке сложных структур данных.

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

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

Если диапазон значений (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].

На практике сортировка подсчетом применяется, когда [math]k = O(n)[/math], а в этом случае время работы алгоритма равно [math]\Theta(n)[/math]

Источники

• Томас Кормен, Чарльз Лейзерсон, Рональд Ривест, Клиффорд Штайн. «Алгоритмы. Построение и анализ» — «Вильямс», 2011 г. — 1296 стр. — ISBN 978-5-8459-0857-5, 5-8459-0857-4, 0-07-013151-1
• Сортировка подсчетом — Википедия