2.9.1 Описание алгоритма

Алгоритм сортировки подсчётом (counting sort) применим, если каждый из п элементов сортируемой последовательности – целое положительное число в известном диапазоне (не превосходящее заранее известного k). Если k = О(п), то алгоритм сортировки подсчётом работает за время О(п).

Идея этого алгоритма заключается в том, чтобы для каждого элемента х предварительно подсчитать, сколько элементов входной последовательности меньше х. Далее х записывается напрямую в выходной массив в соответствии с этим числом (если, скажем, 5 элементов входного массива меньше х, то в выходном массиве х дол­жен быть записан на место номер 6). Если предположить, что в сортируемой последовательности могут присутствовать равные числа, то представленная схема потребует небольшой модификации, позволяющей избежать записи нескольких чисел на одно место.

В приводимом ниже псевдокоде используется вспомогательный массив С[1..k] из k элементов. Входная последовательность записана в массиве А[1..п], отсортированная последовательность записывается в массив В[1..п].

Листинг 2.11 – Алгоритм сортировки подсчетом

Работа алгоритма сортировки подсчётом проиллюстрирована на рис. 2.12. После инициализации (строки 1-2) мы сначала помещаем в C[i] количество элементов массива A, равных i (строки 3-4), а затем, находя частичные суммы последовательности С[1],С[2],...,С[k], – количество элементов, не превосходя­щих i (строки 6-7). Наконец, в строках 9-11 каждый из элементов массива А помещается на нужное место в массиве В. В самом деле, если все п элементов различны, то в отсортированном массиве число A[j] должно стоять на месте номер C[A[j]], потому что именно столько элементов массива А не превосходят A[j]; если в массиве А встречаются повторения, то после каждой записи числа А[i] в массив В число C[A[j]] уменьшается на единицу (строка 11), так что при следующей встрече с числом, равным A[j], оно будет записано на одну позицию левее.

Рисунок 2.12 – Работа алгоритма сортировки подсчетом

На рисунке 2.12 работа алгоритма Counting-Sort, применённого к массиву A[1..8], состоящему из натуральных чисел, не превосходящих k = 6. (а) Массив А и вспомогательный массив С после выполнения цикла в строках 3-4. (б) Массив С после выполнения цикла в строках 6-7. (в-д) Выходной массив В и вспомогательный массив С после одного, двух и трёх повторений цикла в строках 9-11. Затемненные клетки соответствуют элементам массива, значения которым ещё не присвоены. (е) Массив В после окончания работы алгоритма.