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

Question

Почему QuickSort (или INTROSORT) или любой алгоритм сортировки на основе сравнения более распространен, чем Radix-сортировка? Особенно для сортировки номеров.

Radix-сортировка не сравнение на основе сравнения, поэтому может быть быстрее, чем O (nlogn). На самом деле это O (kn), где k - количество битов, используемых для представления каждого элемента. И накладные расходы на память не критичны, поскольку вы можете выбрать количество ведер, и требуемая память может быть меньше требований Mergeort.

Это связано с кэшированием? Или, возможно, доступ к случайным байтам целых чисел в массиве?

Answer 1

Два аргумента приходят на мой взгляд:

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

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

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

2. Radix Сортировка нужно больше памяти.

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

   Если я помню правильно A в месте алгоритм Radix-сорта существует на бумаге, хотя.

Answer 2

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

Answer 3

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

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

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

Другой - это реализация:

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

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

Answer 4

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

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

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

Решающий фактор заключается в том, как распределены ключи. Лучший случай для Radix сортировка сознает то, что они принимаются в качестве последовательных битовых узоров. Это сделает ключи от того, как они могут быть, все еще предполагающие, что они отличаются. Это делает Radix сортировку O (N · log (n)), но сортировки на основе сравнения не будут такими эффективными, поскольку сравнения не будут постоянными временем при этом предположении. Если мы вместо этого предположим, что ключи являются битовыми узорами длины K · log (n) для постоянной K> 1 и журнала Base 2, и что они равномерно случайные, то Radix Sort будет все еще будет O (N · log (n) ), но сортирует сорты на основе сравнения, поскольку «дополнительная» длина делает даже ключи, которые подряд, в отсортированном результате, достаточно отличаются, чтобы сравнения были постоянными в среднем. Если ключевые ключи дольше, чем o (log (n)), но случайные, то Radix сортируют сортируют. Есть много других предположений, которые также могут быть сделаны, и большинство требуют тщательного исследования, чтобы сделать правильное сравнение.

Answer 5

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

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

QuickSort - «безопасный» выбор. Потенциальное время выполнения Radix Sort на основе сортировки подсчета очень привлекательна, да, но Radix сортировка подразумевается для плохо выполнения на вредоносных / несчастных наборах данных. Если число цифр ключей отсортировано, подходит к числу отсортированных ключей, Radix Sort выполняет на N ^ 2 вместе с незначительной сложности пространства, и он имеет тенденцию иметь довольно высокие встроенные константы времени выполнения, отличные от количества цифр ключей отсортированы.
Mergeort привлекателен, потому что его поведение, в некотором роде, аналогично Quicksort, который выбирает оптимальный поворот при каждой возможности (медиану). Тем не менее, он поставляется с заметной космической сложностью. Это не так любезно до злоумышленников / несчастных данных, как Radix, но также не предлагает привлекательное возможное время выполнения. Базовая QuickSort очень хорошо работает на большинстве данных, кроме почти (или полностью) отсортированных и поставляется с крошечной космической сложностью.
Уязвимость QuickSort легко обрабатывалась, преобразовав ее в рандомизированную QuickSort. Уязвимость RADIX сортировки решается путем размещения ограничений на отсортированные ключи, которые по своей природе ограничивают пользователей библиотеки. QuickSort является более исполком, чем сливается на небольшие наборы данных, и разумно выполняется, когда объединение может быть быстрее.
При внедрении библиотеки вы хотите сделать его в целом полезным. Возьмите эти примеры, веб-приложение и небольшое устройство с чрезвычайно ограниченным микроконтроллером. Веб-приложения должны иметь дело с вредоносными данными на регулярной основе, а также иметь широкий спектр потребностей. Библиотека с предварительным условием ограничений менее вероятно, будет полезной. В случае микроконтроллера он может быть ограничен в пространстве и не может отказаться от малейшего бита, где можно сохранить. QuickSort сохраняет пространство, и завершит только медленнее постоянным множеством, если возникает ситуация, что она медленнее.
В сумме -
1.) Библиотеки часто кодируются как можно большего пользования
2.) Хорошая производительность, все вокруг приемлемо, особенно если оно во многих случаях, лучшая производительность
3.) Пространство не всегда является первичной проблемой, но когда оно так часто явно ограничительно

Answer 6

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

Best Case Quick Sort = O (n. Log n) где n = количество ключей в наборе входных клавиш.

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

Radix Sort = 16 * 6 = 96 единиц времени. Quick Sort = 16 * 4 = 64 единицы времени.

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