Изменения

Перейти к: навигация, поиск

Цифровая сортировка

921 байт добавлено, 21:13, 21 мая 2012
Алгоритм
Примерами объектов, которые удобно разбивать на разряды и сортировать по ним, являются числа и строки.
 *Для чисел уже существует понятие разряда, поэтому разбивать будем именно по ним. Конечно, в разных системах счисления разряды одного и того же числа отличаются, поэтому перед тем как разбивать число, представим его в удобной для нас системе счисления. *Так как строки представляют из себя массивы символов, то в качестве разряда можно брать отдельные символы, сравнение которых обычно происходит по соответствующим им кодам из [[Представление символов, таблицы кодировок#Таблицы кодировок|таблицы кодировок]]. Для такого разбиения самый младший разряд {{---}} последний символ строки.*Для чисел вышеперечисленных объектов наиболее часто в качестве устойчивой сортировки применяют [[сортировка подсчетом|сортировку подсчетом]], так как количество различных значений разрядов обычно невелико по сравнению с количеством сортируемых объектов.
=== Корректность алгоритма ===
Докажем, что данный алгоритм работает верно, используя метод математической индукции по номеру разряда. Пусть <tex> n </tex> {{---}} количество разрядов в сортируемых объектах.
403
правки

Навигация