Почему быстрая сортировка более популярна, чем сортировка по основанию?
Почему быстрая сортировка (или интросортировка) или любой алгоритм сортировки на основе сравнения более распространен, чем radix-sort? Особенно для сортировки чисел.
] Radix-sort не основан на сравнении, поэтому может быть быстрее, чем O (n logn). Фактически это O (k n), где k - количество битов, используемых для представления каждого элемента. И объем памяти не критичен, так как вы можете выбрать количество используемых сегментов, и требуемая память может быть меньше требований mergesort.
Это связано с кэшированием? Или, возможно, получить доступ к случайным байтам целых чисел в массиве?
3 ответа
Мне приходят на ум два аргумента:
Quicksort / Introsort более гибок:
Quicksort и Introsort хорошо работают со всеми видами данных. Все, что вам нужно для сортировки, - это возможность сравнивать товары. С числами это тривиально, но вы можете сортировать и другие данные.
С другой стороны, Radix sort просто сортирует объекты по их двоичному представлению. Он никогда не сравнивает предметы друг с другом.
Радиксной сортировке требуется больше памяти.
Все реализации поразрядной сортировки, которые я видел, используют вторичный буфер для хранения результатов частичной сортировки. Это увеличивает требования к памяти для алгоритма сортировки. Это может не быть проблемой, если вы отсортируете только пару килобайт, но если вы перейдете в диапазон гигабайт, это будет иметь огромное значение.
Если я правильно помню, на бумаге существует алгоритм поразрядной сортировки.
Радиксная сортировка медленнее для (большинства) реальных случаев использования.
Одной из причин является сложность алгоритма:
Если элементы уникальны, k >= log(n). Даже при наличии дублирующихся элементов набор задач, в которых k < log(n), невелик.
Другая проблема - реализация:
Дополнительное требование памяти (что само по себе является недостатком), отрицательно сказывается на производительности кэша.
Я думаю, можно с уверенностью сказать, что многие библиотеки, например, стандартная библиотека, используют Quicksort, потому что в большинстве случаев он работает лучше. Я не думаю, что "сложная реализация" или "менее интуитивно понятный" являются основными факторами.
Один очевидный ответ заключается в том, что вы можете сортировать произвольные типы с помощью быстрой сортировки (т. е. все, что сопоставимо), в то время как вы ограничены числами только с основанием. И быстрая сортировка IMO намного более интуитивно понятна.