403
правки
Изменения
м
→Алгоритм
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Для простоты рассуждений будем предполагать, что объекты сортируются по неубыванию. Пусть <tex> n </tex> {{---}} количество разрядов в сортируемых объектах.
*База: <tex> n = 1 </tex>. Очевидно, что алгоритм работает верно, потому что в таком случае мы просто сортируем младшие разряды какой-то заранее выбранной стабильной сортировкой.
*Переход: Пусть для <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>.
