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

Почему quicksort (или introsort), или любой алгоритм сортировки на основе сравнения чаще, чем сортировка radix? Специально для сортировки чисел.

Radix-sort не основан на сравнении, поэтому может быть быстрее, чем O (n logn). Фактически, это O (k n), где k – количество бит, используемых для представления каждого элемента. И накладные расходы на память не являются критическими, так как вы можете выбрать количество используемых ведер, а требуемая память может быть меньше требований mergesort.

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

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

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

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

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

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

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

    Однако, если я помню, что на бумаге существует алгоритм сортировки по методу «на месте».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Быстрая производительность: сортировка массивов
  • Алгоритм естественной сортировки
  • Список C # Сортировать по x, тогда y
  • Какой тип сортировки используется в std :: sort ()?
  • Очень запутано в выводе типа Java 8 Comparator
  • Сортировка двухмерного массива на основе одного столбца
  • Закажите «смешанный» вектор (цифры с буквами)
  • Как выполнить естественную сортировку?
  • Сортировка списка с адаптером массива
  • Сортировка ObservableCollection C #
  • Как отсортировать двумерный массив в C #?
  • Давайте будем гением компьютера.