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-значными числами.

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