Почему быстрая сортировка более популярна, чем радикальная?

На ум приходят два аргумента:

1. Quicksort / Introsort более гибок:

   Quicksort и Introsort хорошо работают со всеми видами данных. Все, что вам нужно для сортировки, - это возможность сравнивать товары. С числами это тривиально, но вы можете сортировать и другие данные.

   С другой стороны, Radix sort просто сортирует вещи по их двоичному представлению. Он никогда не сравнивает предметы друг с другом.

2. Для сортировки Radix требуется больше памяти.

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

   Если я правильно помню, на бумаге существует алгоритм поразрядной сортировки.

Один очевидный ответ заключается в том, что вы можете сортировать произвольные типы с помощью быстрой сортировки (то есть все, что сопоставимо), в то время как вы ограничены числами только с основанием системы счисления. И быстрая сортировка IMO намного более интуитивно понятна.

Сортировка Radix медленнее для (большинства) реальных случаев использования.

Одна из причин - сложность алгоритма:

Если элементы уникальны, k> = log (n). Даже с повторяющимися элементами набор задач, где k ‹log (n) невелик.

Другой вариант:

Требование дополнительной памяти (что само по себе является недостатком) отрицательно сказывается на производительности кеша.

Я думаю, можно с уверенностью сказать, что многие библиотеки, например стандартная, используют Quicksort, потому что в большинстве случаев он работает лучше. Я не думаю, что «сложная реализация» или «менее интуитивно понятный» являются основными факторами.

Как упоминалось в Википедии

Тема эффективности поразрядной сортировки по сравнению с другими алгоритмами сортировки несколько сложна и вызывает множество недоразумений. Будет ли поразрядная сортировка столь же эффективной, менее или более эффективной, чем у лучших алгоритмов, основанных на сравнении, зависит от деталей сделанных предположений. Эффективность сортировки по системе Radix составляет O (d · n) для n ключей, содержащих d или меньше цифр. Иногда d представляется как константа, что сделало бы сортировку по основанию лучше (для достаточно больших n), чем лучшие алгоритмы сортировки на основе сравнения, которые требуют O (n · log (n)) числа сравнений. Однако в целом d нельзя считать константой. В частности, при общепринятом (но иногда неявном) предположении, что все ключи различны, тогда d должен иметь порядок не менее log (n), что дает в лучшем случае (с плотно упакованными ключами) временную сложность O (п · журнал (п)). Казалось бы, это делает сортировку по основанию не менее эффективной, чем лучшие сортировки на основе сравнения (и хуже, если ключи намного длиннее, чем log (n)).

Аргумент счетчика - основанные на сравнении алгоритмы измеряются количеством сравнений, а не фактической временной сложностью. При некоторых предположениях сравнения будут в среднем постоянными по времени, при других - нет. Сравнение случайно сгенерированных ключей в среднем занимает постоянное время, так как ключи различаются по самому первому биту в половине случаев и различаются по второму биту в половине оставшейся половины и т. Д., В результате чего получается в среднем два бита, которые нужно сравнивать. В алгоритме сортировки первые выполненные сравнения удовлетворяют условию случайности, но по мере продвижения сортировки сравниваемые ключи явно больше не выбираются случайным образом. Например, рассмотрим сортировку слиянием снизу вверх. Первый проход сравнивает пары случайных ключей, но последний проход сравнивает ключи, которые очень близки по порядку сортировки.

Решающим фактором является способ распределения ключей. Лучшим случаем для поразрядной сортировки является то, что они используются как последовательные битовые комбинации. Это сделает ключи настолько короткими, насколько это возможно, при условии, что они различны. Это делает сортировку по основанию O (n · log (n)), но сортировка на основе сравнения не будет столь эффективной, поскольку при этом предположении сравнения не будут иметь постоянного времени. Если вместо этого мы предположим, что ключи представляют собой битовые комбинации длины k · log (n) для константы k ›1 и log по основанию 2, и что они равномерно случайны, то сортировка по основанию системы счисления все равно будет O (n · log (n) ), но то же самое будет и с сортировкой на основе сравнения, поскольку дополнительная длина делает даже ключи, которые являются последовательными в отсортированном результате, достаточно разными, чтобы сравнения были в среднем постоянным временем. Если ключи длиннее O (log (n)), но случайны, то сортировка по основанию будет хуже. Есть много других предположений, которые также можно сделать, и большинство из них требует тщательного изучения, чтобы сделать правильное сравнение.

Пункты, указанные в других ответах, действительны, но, насколько ваше беспокойство упоминается в нескольких комментариях

... тот факт, что стандартные алгоритмы сортировки чисел реализованы с использованием быстрой сортировки. Особенно реализации в библиотеках ...

Quicksort - это «безопасный» выбор. Потенциальное время выполнения поразрядной сортировки, основанной на подсчетной сортировке, очень привлекательно, да, но радиксная сортировка может плохо работать с вредоносными / неудачными наборами данных. Если количество цифр в сортируемых ключах приближается к количеству сортируемых ключей, сортировка по основанию выполняется на n ^ 2 вместе с немаловажной пространственной сложностью и, как правило, имеет довольно высокие встроенные константы времени выполнения, отличные от числа цифр сортируемых ключей.
Сортировка слиянием привлекательна тем, что ее поведение в некотором смысле аналогично быстрой сортировке, которая выбирает оптимальную точку поворота при каждой возможности (медиана). Однако он имеет значительную пространственную сложность. Он не так подвержен вредоносным / неудачным данным, как radix, но также не предлагает привлекательной возможной среды выполнения. Базовая быстрая сортировка очень хорошо работает с большинством наборов данных, за исключением почти (или полностью) отсортированных, и имеет крошечную пространственную сложность.
Уязвимость быстрой сортировки легко устраняется путем преобразования ее в рандомизированную быструю сортировку. Уязвимость Radix sort устраняется путем наложения ограничений на сортируемые ключи, что по сути ограничивает пользователей библиотеки. Быстрая сортировка более производительна, чем слияние для небольших наборов данных, и работает разумно, когда слияние может быть быстрее.
При реализации библиотеки вы хотите сделать ее универсальной. Возьмем эти примеры, веб-приложение и небольшое устройство с чрезвычайно ограниченным микроконтроллером. Веб-приложениям необходимо регулярно обрабатывать вредоносные данные, а также решать самые разные задачи. Библиотека с предварительно обусловленными ограничениями вряд ли окажется полезной. В случае микроконтроллера он может быть ограничен по пространству и не может отдать ни малейшего бита там, где его можно сохранить. Быстрая сортировка экономит место и будет работать медленнее с постоянным множителем, ЕСЛИ возникнет ситуация, что она медленнее.
В итоге -
1.) Библиотеки часто кодируются для максимально общего удобства использования
2. ) Хорошая производительность во всех отношениях приемлема, особенно если во многих случаях это лучшая производительность.
3.) Пространство не всегда является основной проблемой, но когда это так, это часто явно ограничивает

Эффективность сортировки Radix = O (c.n), где c = наибольшее количество цифр среди набора ключей ввода. n = количество клавиш в наборе клавиш ввода.

Лучший случай быстрой сортировки = O (n. Log n), где n = количество ключей в наборе ключей ввода.

Предположим, что нужно отсортировать 16 номеров по 6 цифр в каждом:

Radix sort = 16 * 6 = 96 единиц времени. Быстрая сортировка = 16 * 4 = 64 единицы времени.

Урок: когда c меньше, Radix действительно выигрывает. Когда он высокий, он проигрывает. Быстрая сортировка не зависит от количества цифр в ключе, что делает ее несколько лучше и более практичной.