Изменения

'''Цифровая сортировка''' — (англ. ''radix sort'') {{---}} один из алгоритмов сортировки, использующих внутреннюю структуру сортируемых объектов.

В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве устойчивой сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> размера <tex> m n </tex>-разрядных чисел размера <tex> n m </tex>-разрядных чисел . Сам по себе алгоритм представляет собой цикл по номеру разряда, на каждой итерации которого элементы массива <tex> A </tex> размещаются в нужном порядке во вспомогательном массиве <tex> B </tex>. Для подсчета количества объектов, <tex> i </tex>-й разряд которых одинаковый, а затем и для определения положения объектов в массиве <tex> B </tex> используется вспомогательный массив <tex> C </tex>. Функция <tex> \mathrm{digit(x, i)} </tex> возвращает <tex> i </tex>-й разряд числа <tex> x </tex>. Также считаем, что значения разрядов меньше <tex> k </tex>.

cnt[j]++--