DAA - Radix Sort

Radix sort - это небольшой метод, который многие люди интуитивно используют при алфавитном расположении большого списка имен. В частности, список имен сначала сортируется по первой букве каждого имени, то есть имена расположены в 26 классах.

Интуитивно понятно, что можно отсортировать числа по их наиболее значимым цифрам. Однако сортировка Radix работает нелогично, сначала сортируя младшие разряды. На первом проходе все числа сортируются по младшей цифре и объединяются в массив. Затем на втором проходе все числа снова сортируются по вторым младшим разрядам и объединяются в массив и так далее.

 Algorithm: Radix-Sort (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]) 
   list = combinebuckets() 
   shift = shift * 10 

Анализ

Каждая клавиша просматривается сразу для каждой цифры (или буквы, если клавиши алфавитные) самой длинной клавиши. Следовательно, если самый длинный ключ имеет m цифр и n ключей, радикальная сортировка имеет порядок O (mn) .

Однако, если мы посмотрим на эти два значения, размер ключей будет относительно небольшим по сравнению с количеством ключей. Например, если у нас есть шестизначные ключи, у нас может быть миллион разных записей.

Здесь мы видим, что размер ключей несущественен, и этот алгоритм имеет линейную сложность O (n) .

пример

Следующий пример показывает, как сортировка Radix работает с семью 3-значными числами.

вход 1- й проход 2- й проход 3- й проход
329 720 720 329
457 355 329 355
657 436 436 436
+839 457 +839 457
436 657 355 657
720 329 457 720
355 +839 657 +839

В приведенном выше примере первый столбец является входным. Остальные столбцы показывают список после последовательных сортировок в позиции все более значимых цифр. Код для сортировки Radix предполагает, что каждый элемент в массиве A из n элементов имеет d цифр, где цифра 1 - цифра самого младшего разряда, а d - цифра высшего порядка.