Когда подходящее время для использования Radix Sort?

Question

Каковы ограничения на ваши данные, чтобы вы могли использовать сортировку Radix?

Если я сортирую большой список целых чисел, было бы целесообразно использовать сортировку Radix? Почему сортировка Radix не используется больше?

Answer 1

Замечательно, когда у вас есть большой набор данных с ключами, которые каким-то образом ограничены. Например, когда вам нужно заказать 1-миллионный массив из 64-битных чисел, его можно использовать для сортировки по 8 наименее значимых бит, затем к следующим 8 и т. Д. (Применяется 8 раз). Таким образом, этот массив можно отсортировать в 8 * 1M операциях, а не 1M * log (1M).

Answer 2

Если вы знаете диапазон целочисленных значений, и это не слишком большой,
возможно counting sort будет лучшим выбором в вашем случае.

Answer 3

Одна из причин, по которой вы, возможно, не увидите это так часто, как вы думаете, это то, что сортировка Radix не такая общая цель, как сортировка (quicksort/mergesort/heapsort). Это требует, чтобы вы могли представлять элементы, которые нужно сортировать как целое, или что-то вроде целого. При использовании стандартной библиотеки легко определить функцию сравнения, которая сравнивает произвольные объекты. Может быть сложнее определить кодировку, которая правильно отображает ваш произвольный тип данных в целое число.

Answer 4

Сортировка ковша полезна в ситуациях, когда количество дискретных значений ключа невелико относительно количества элементов данных и где цель состоит в том, чтобы создать повторно отсортированную копию списка, не нарушая оригинала (так что необходимо поддерживать как старые, так и новые версии списка одновременно не является бременем). Если количество возможных клавиш слишком велико для обработки за один проход, можно расширить сортировку ведра в сортировку по основанию, сделав несколько проходов, но один теряет большую часть преимуществ скорости, которые может предложить сортировка ковша для небольших клавиш.

В некоторых сценариях внешней сортировки, особенно когда количество различных значений ключей очень мало (например, два), требуется стабильная сортировка, а устройство ввода-вывода может эффективно работать только с одним последовательным потоком данных, это может быть полезно, чтобы сделать K проходит через поток исходных данных, где K - количество ключевых значений. На первом проходе копируются все элементы, где ключ является минимальным допустимым значением и пропускает остальное, а затем копирует все элементы, где ключ является следующим более высоким значением, пропуская остальные и т. Д. Этот подход, очевидно, будет ужасно эффективным если есть очень много разных ключевых значений, но будет неплохо, если их два.