403
правки
Изменения
→Псевдокод
*Переход: Пусть для <tex> n = k </tex> алгоритм правильно отсортировал элементы по <tex> k </tex> младшим разрядам. Покажем, что в таком случае, при сортировке по <tex> (k + 1) </tex>-ому разряду, объекты также будут отсортированы в правильном порядке. Вспомогательная сортировка разобьет все объекты на группы, в которых <tex> (k + 1) </tex>-ый разряд объектов одинаковый. Рассмотрим такие группы. Для сортировки по отдельным разрядам мы используем стабильную сортировку, следовательно порядок объектов с одинаковым <tex> (k + 1) </tex>-ым разрядом не изменился. Но по предположению индукции по предыдущим <tex> k </tex> разрядам объекты были отсортированы правильно, и поэтому в каждой такой группе объекты будут отсортированы верно. Также верно, что сами группы находятся в правильном относительно друг друга порядке, а следовательно и все элементы отсортированы правильно по <tex> (k + 1) </tex>-ым младшим разрядам.
== Псевдокод ==
В качестве примера рассмотрим сортировку чисел. Как говорилось выше, в такой ситуации в качестве стабильной сортировки применяют сортировку подсчетом, так как обычно количество различных значений разрядов не превосходит количества сортируемых элементов. Ниже приведен псевдокод цифровой сортировки, которой подается массив <tex> A </tex> <tex> m </tex>-разрядных чисел размера <tex> n </tex>. Функция <tex> digit(x, i) </tex> возвращает <tex> i </tex>-ый разряд числа <tex> x </tex>. Так же считаем, что значения разрядов меньше <tex> k </tex>. Radix_sortradix_sort(A) for i = 1 to m do устойчивая сортировка for j = 0 to k - 1 // обнуление вспомогательного массива С, C[j] = 0; // использующегося в качестве счетчика for j = 0 to n - 1 C[digit(A[j], i)] = C[digit(A[j], i)] + 1; for j = 1 to k - 1 C[j] = C[j] + C[j - 1]; for j = n - 1 to 0 // заполняем вспомогательный массив B, в котором после каждой итерации B[C[digit(A[j], i)]] = A[j]; // внешнего цикла числа отсортированы по младшим i битам C[digit(A[j], i)] = C[digit(A[j], i)] -ому разряду1; A = B;
==Сложность==
