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

Сортировка подсчетом ("черпачная")

Применение:
сортируемые числа имеют диапазон возможных целых положительных значений, который достаточно мал по сравнению с сортируемым множеством

Алгоритм:
1) Пусть есть массив А из N элементов, включающий числа в диапазонее от 0 до k-1 (то есть всего максимум k различных значений)
2) Создать вспомогательный массм C[0..k-1], состоящий из нулей (его можно назввать массивом счетчиков)
3) Последовательно прочитать элементы массива А и для каждого А[i] увеличить С[A[i]] на единицу
В итоге мы получим массив С, в котором каждый элемент C[i] равен числу встречаемости числа в исходном массиве А, индекс i указывает на число массива А
4) Далее можно сформировать отсортированный массив, проходясь по массиву С и для каждого j от 0 до k-1 в новый массив (или тот же массив А) последовательно записать число j C[j] раз

Пример:
Пусть имеет массив А = {2, 5, 6, 9, 4, 1, 8, 2, 9, 8, 4, 1, 4, 1}
Диапазон чисел - от 0 до 9, то есть всего 10 различных значений
1. Создаем массив С из 10 нулевых элементов
2. Проходим по массиву А и увеличиваем на 1 элемент C[A[i]]
3. Полученный массив С = {0, 3, 2, 0, 3, 1, 1, 0, 2, 2}

Данный метод можно применять и при наличии отрицательных значений, в этом случае для подсчета количества элементов равных самому минимальному можно использовать элемент С[0], выполняя соответствующую сдвижку C[i - min]

Пример реализации на алгоритмическом языке:
для i от 1 до (длина массива А):
    C [A[i]] += 1