Поскольку все алгоритмы сортировки сортировки занимают не менее n lg n, зачем нам когда-либо понадобиться использовать что-то вроде quicksort, когда мы можем выражать элементы в списке quicksort как биты и использовать что-то вроде линейки radix?Если существуют линейные алгоритмы сортировки по времени, такие как Radix Sort, когда нам нужно использовать сортировки сравнения?
Соотношение Radix имеет тенденцию демонстрировать плохую локальность кэша, см., Например, this paper для анализа различных алгоритмов сортировки под воздействием кеша (переходите к выводу о том, что для определения местоположения плохого кэша сортировки по методу быстрой сортировки и слияния). Quicksort и mergesort разделяют данные таким образом, что после нескольких итераций раздел будет поместиться в нескольких строках кэша, тогда как сортировка по методу radix продолжает перетасовывать данные. Кроме того, для сортировки radix необходимо использовать связанные структуры данных для своих ковшей (которые демонстрируют плохую производительность кэша), или же им нужно использовать сверхбольшие массивы (которые теряют память).
Кроме того, в зависимости от размера основания radix sort его постоянный коэффициент может быть больше, чем лог-фактор quicksort/mergesort. В крайнем случае, используя радиус 2 в 64-битных целых числах, сортировка radix имеет постоянный коэффициент в 64 (один проход на бит), тогда как маловероятно, чтобы лог-фактор quicksort/mergesort был таким большим (поскольку это означало бы, что вы сортируете 2^64 элемента)
Ваш второй пункт особенно ясен, когда элементы не являются скалярными значениями. Представьте, что вы пытаетесь использовать сортировку radix в массиве из 100 символов. –
Вы обсуждаете только дрянные реализации рода LSD radix. Хорошая реализация сортировки по методу MSD не имеет ни одной из проблем, которые вы предлагаете на равномерно распределенных входах. – tmyklebu
@JimMischel: Как это происходит, сортировка radix - это то, что люди используют для сортировки больших массивов из 100-символьных строк. (Или, по крайней мере, разбить его на кучу массивов достаточно коротким, чтобы сортировка в кэше была подходящей.) – tmyklebu
Современные реализации mergesort с использованием ядра SIMD для сортировки коротких массивов могут быть очень и очень быстрыми. This paper by some folks at Intel описывает одну такую реализацию. Главным преимуществом здесь является то, что ядро SIMD может выполнять несколько сравнений и свопов за такт, получая и используя несколько бит информации о массиве, который будет сортироваться за такт.
Для быстрой сортировки требуется тест, магазин и приращение одного из двух указателей на каждой итерации, которая образует одну огромную цепочку зависимостей. Это не очень удобно, поскольку это означает, что вы получаете один бит информации о массиве каждые несколько тактов.
У подобных решений есть такая же проблема, как и Quicksort (каждый проход представляет собой одну огромную цепочку зависимостей с доступом и приращением одного указателя из довольно большого, равномерно распределенного набора). Однако на равномерно распределенных входах правильно подобранная сортировка MSD с использованием пяти- или шестибитовых ключей может сделать за один проход над входом, что Quicksort займет пять или шесть проходов. В последнее время я не приурочил этот материал, но хорошая сортировка по методу MSD по-прежнему может быть лучшим способом сортировки больших массивов int s или long long.
Ничего подобного из-за сортировки radix будет держать вас в тепле ночью, если ваш вход плохо распределен, а вселенная возможных ключей велика по сравнению с количеством клавиш на вашем входе.
Потому что не все можно правильно сравнить, просто сравнивая его биты. Например, моя логика для 'foo1
AndyG
Но плавающая точка - это просто 32 бита, так что вы говорите, что для более низких чисел quicksort лучше, хотя, конечно, асимптотически это не так? – Alkorizm
Я вижу, но вы не могли бы сделать какой-то цельный ключ для своей логики? Разве это не сработает? – Alkorizm