Корневая сортировка При корневой сортировке упорядочивание списка происходит без непосредственного сравнения ключевых значений между собой. При этом создается набор «стопок», а элементы распределяются по стопкам в зависимости от значений ключей. Собрав значения обратно и повторив всю процедуру для последовательных частей ключа, мы получаем отсортированный список. Чтобы такая процедура работала, распределение по стопкам и последующую сборку следует выполнять очень аккуратно.
Подобная процедура используется при ручной сортировке карт. В некоторых библиотеках в докомпьютерные времена при выдаче книги заполнялась карта выдачи. Карты выдачи были занумерованы, а сбоку на них проделывался ряд выемок – в зависимости от номера карты. При возвращении книги карта выдачи удалялась, и ее клали в стопку. Затем вся стопка прокалывалась длинной иглой на месте первой выемки, и иглу поднимали. Карты с удаленной выемкой оставались на столе, а остальные были наколоты на иглу. Затем две получившиеся стопки переставлялись так, что карточки на игле шли за карточками с отверстиями. Затем игла втыкалась в месте второй выемки и весь процесс повторялся. После прокалывания по всем позициям карты оказывались в порядке возрастания номеров.
Добавлено (14.03.2008, 23:57)
---------------------------------------------
Эта процедура ручной обработки разделяет карты по значению младшего разряда номера на первом шаге и старшего разряда на последнем. Компьютеризованный вариант этого алгоритма использует 10 стопок:
RadixSortClist,N)
list сортируемый список элементов
N число элементов в списке
shift=l
for loop=l to keySize do
for entry=l to N do
bucketNumber=(list[entry].key/shift) mod 10
Append(bucket[bucketNumber], list[entry])
end for entry
list=CombineBuckets ()
shift=shift*10
end for loop
keySize – самый большой разряд числа;
10 – количество цифр
bucket – стопка.
Добавлено (14.03.2008, 23:58)
---------------------------------------------
Начнем с обсуждения этого алгоритма. При вычислении значения переменной bucketNumber из ключа вытаскивается одна цифра. При делении на shift ключевое значение сдвигается на несколько позиций вправо, а последующее применение операции mod оставляет лишь цифру единиц полученного числа. При первом проходе с величиной сдвига 1 деление не меняет числа, а результатом операции mod служит цифра единиц ключа. При втором проходе значение переменной shift будет уже равно 10, поэтому целочисленное деление и последующее применение операции mod дают цифру десятков. При очередном проходе будет получена следующая цифра числа.
Функция CombineBuckets вновь сводит все стопки от bucket [0] до bucket [9] в один список. Этот переформированный список служит основой для следующего прохода. Поскольку переформирование стопок идет в определенном порядке, а числа добавляются к концу каждой стопки, ключевые значения постепенно оказываются отсортированными.
