Описание алгоритма. Сортировка подсчетом

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

Алгоритм сортировки подсчётом (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. Затемненные клетки соответствуют элементам массива, значения которым ещё не присвоены. (е) Массив В после окончания работы алгоритма.