Сортировка подсчетом - Алгоритмика (original) (raw)

Все предыдущие алгоритмы работали с массивами, в которых лежат могут лежать абсолютно любые объекты, которые можно сравнивать: числа, строки, пары, другие массивы — почти все что угодно.

В особом случае, когда элементы могут принадлежать только какому-то небольшому множеству, можно использовать другой алгоритм — сортировку подсчетом (англ. counting sort).

Пусть, например, нам гарантируется, что все числа натуральные и лежат в промежутке от 111 до 100100100. Тогда есть такой простой алгоритм:

• Создадим массив размера 100100100, в котором будем хранить на kkk-ом месте, сколько раз число kkk встретилось в этом массиве.
• Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на 111.
• После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести 111 столько раз, сколько встретилась 111, вывести 222 столько раз, сколько встретилась 222, и так далее.

Время работы такого алгоритма составляет O(m+n)O(m + n)O(m+n), где mmm — число возможных значений, nnn — число элементов в массиве. Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчетом является одним из самых оптимальных решений.

#Вариант реализации

Создадим массив ccc размера 100100100 и заполним его, один раз пройдясь по исходному массиву.

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

void count_sort(int *a, int n) {
    int c[100] = {0};

    for (int i = 0; i < n; i++)
        c[a[i]]++;

    int k = 0;
    for (int i = 0; i < 100; i++)
        while (c[i]--)
            a[k++] = i;
}