Все предыдущие алгоритмы работали с массивами, в которых лежат могут лежать абсолютно любые объекты, которые можно сравнивать: числа, строки, пары, другие массивы — почти все что угодно.
В особом случае, когда элементы могут принадлежать только какому-то небольшому множеству, можно использовать другой алгоритм — сортировку подсчетом (англ. counting sort).
Пусть, например, нам гарантируется, что все числа натуральные и лежат в промежутке от $1$ до $100$. Тогда есть такой простой алгоритм:
- Создадим массив размера $100$, в котором будем хранить на $k$-ом месте, сколько раз число $k$ встретилось в этом массиве.
- Пройдемся по всем числам исходного массива и увеличим соответствующее значение массива на $1$.
- После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести $1$ столько раз, сколько встретилась $1$, вывести $2$ столько раз, сколько встретилась $2$, и так далее.
Время работы такого алгоритма составляет $O(m + n)$, где $m$ — число возможных значений, $n$ — число элементов в массиве. Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчетом является одним из самых оптимальных решений.
#Вариант реализации
Создадим массив $c$ размера $100$ и заполним его, один раз пройдясь по исходному массиву.
Затем заведем указатель $k$ на позицию в исходном массиве, куда нужно записывать очередное число, и будем увеличивать его каждый раз, когда мы уменьшаем очередную ячейку в $c$.
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;
}