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

Ответ 1

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

• Quicksort/Introsort более гибкий:

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

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

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

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

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

Ответ 2

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

Ответ 3

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

Одна из причин заключается в сложности алгоритма:

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

Еще одна реализация:

Дополнительная потребность в памяти (которая сама по себе является недостатком) отрицательно влияет на производительность кэша.

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

Ответ 4

Как упоминалось в Wikipedia

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

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

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

Ответ 5

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

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

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

Ответ 6

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

Быстрый порядок сортировки = O (n. log n) где n = количество ключей в наборе входных ключей.

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

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

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