Корневая сортировка

Корневая сортировка

    При корневой сортировке упорядочивание списка происходит без непосредственного сравнения ключевых значений между собой. При этом создается набор "стопок", а элементы распределяются по стопкам в зависимости от значений ключей. Собрав значения обратно и повторив всю процедуру для последовательных частей ключа, мы получаем отсортированный список. Чтобы такая процедура работала, распределение по стопкам и последующую сборку следует выполнять очень аккуратно.
    Подобная процедура используется при ручной сортировке карт. В некоторых библиотеках в докомпьютерные времена при выдаче книги заполнялась карта выдачи. Карты выдачи были занумерованы, а сбоку на них проделывался ряд выемок - в зависимости от номера карты. При возвращении книги карта выдачи удалялась, и ее клали в стопку. Затем вся стопка прокалывалась длинной иглой на месте первой выемки, и иглу поднимали. Карты с удаленной выемкой оставались на столе, а остальные были наколоты на иглу. Затем две получившиеся стопки переставлялись так, что карточки на игле шли за карточками с отверстиями. Затем игла втыкалась в месте выемки и весь процесс повторялся. После прокалывания по всем позициям карты оказывались в порядке возрастания номеров.
    Эта процедура ручной обработки разделяет карты по значению младшего разряда номера на первом шаге и старшего разряда на последнем. Компьютеризированные вариант этого алгоритма использует 10 стопок:

RadixSort(list, N)	
list			сортируемый список элементов
N				число элементов в списке

shift  = 1
for loop = 1 to keySize do
	for entry = 1 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

Начнем с обсуждения этого алгоритма. При вычислении значения переменной bucketNumber из ключа вытаскивается одна цифра. При делении на shift ключевое значение сдвигается на несколько позиций вправо, а последующее применение операции mod оставляет лишь цифру единиц полученного числа. При первом проходе с величиной сдвига 1 деление не меняет числа, а результатом операции mod служит цифра единиц ключа. При втором проходе значение переменной shift будет уже равно 10, поэтому целочисленное деление и последующее применение операции mod дают цифру десятков. При очередном проходе будет получена следующая цифра числа.
Функция CombineBuckets вновь сводит все стопки от bucket[0] до bucket[9] в один список. Этот переформированный список служит основой для следующего прохода. Поскольку переформирование стопок идет в определенном порядке, а числа добавляются к концу каждой стопки, ключевые значения постепенно оказываются отсортированными.

Исходный список:

310

213

023

130

013

301

222

032

201

111

323

002

330

102

231

120

Номер стопки	Содержимое
0	310	130	330	120
1	301	201	111	231
2	222	032	002	102
3	023	023	013	323

(а) Первый проход, разряд единиц

Список, полученный в результате первого прохода:

310

130

330

120

301

201

111

231

222

032

002

102

213

023

013

323

Номер стопки	Содержимое
0	301	201	002	102
1	310	111	213	013
2	120	222	023	323
3	130	330	231	032

(б) Второй проход, разряд десятков

Список, полученный в результате второго прохода:

301

201

002

102

310

111

213

013

120

222

023

323

130

330

231

032

Номер стопки	Содержимое
0	002	013	023	032
1	102	111	120	130
2	201	213	222	231
3	301	310	323	330

(в) Третий проход, разряд сотен

Здесь показаны три прохода на списке трехзначных чисел. Для упрощения примера в ключах используются только цифры от 0 до 3, поэтому достаточно четырех стопок.
При взгляде на (в) становится ясно, что если вновь собрать стопки по порядку, то получится отсортированный список.

Сайт управляется системой uCoz