Изменения

При цифровой сортировке данные разбиваются Пусть у нас есть множество последовательностей одинаковой длины, состоящих из элементов, на "разряды"которых задано [[Отношение порядка|отношение линейного порядка]]. Требуется отсортировать эти последовательности в лексикографическом порядке. По аналогии с разрядами чисел будем называть элементы, после чего они сортируются из которых состоят сортируемые объекты, разрядами. Сам алгоритм состоит в последовательной сортировке объектов какой-либо устойчивой сортировкой по каждому разряду, в порядке от младшего разряда к старшему. Заметим, что лексикографический порядок сортировки разрядов должен совпадать с требуемым от самой цифровой сортировки. Например, если объекты сортируются по невозрастанию, то при сортировки по <tex> i </tex>-ому разряду объект с меньшим <tex> i </tex>-ым разрядом должен идти раньше, чем объект, у которого данный разряд больше. В этом нетрудно убедиться, если на вход алгоритму подать объекты, состоящие из одного разрядапосле чего последовательности будут расположены в требуемом порядке.

*Для чисел уже существует понятие разряда, поэтому разбивать будем именно по нимпредставлять числа как последовательности разрядов. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед тем как разбивать число, сортировкой представим его числа в удобной для нас системе счисления.

*Так как строки Строки представляют из себя массивы последовательности символов, то поэтому в качестве разряда можно брать разрядов в данном случае выступают отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из [[Представление символов, таблицы кодировок#Таблицы кодировок|таблицы кодировок]]. Для такого разбиения самый младший разряд {{---}} последний символ строки.

<b> Переход</b>: Пусть для <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>-м младшим разрядам.