Сложность слепого рода?

9

Все мы знаем, что минимальная сложность алгоритма сортировки на основе сравнения Ω(NжурналN)сравнения. Я пытаюсь сделать слепой сортировку, т.е. с учетом числаN вывести схему (с логическими, арифметическими и "сравнительными" вентилями), которая сортирует список N Предметы.

Предварительный расчет всех сравнений и последующее выполнение арифметики с полученными битами дает мне алгоритм , однако с помощью какой-то безумной "арифметики с указателями" я думаю, что могу получить(N2)Θ(N3)Θ(N2) версия.

Существует ли известная нижняя граница для схем сортировки на основе сравнения вдоль линий, аналогичных для алгоритма сортировки на основе сравнения? Может ли быть вообще возможна слепая сортировка в раз?NжурналNNжурналN

Бристоль
источник
1
Каков ваш фон? ты искал вокруг этого? например, бионический сортировщик дает хорошую сеть с размером , и время для создания соответствующей сети не превышает размер сети. О(Nжурнал2N)
Саид
Я имею опыт криптографии, и я смотрю на сортировку секретных данных, что дает довольно необычные ограничения на относительную стоимость операций. Я задаюсь вопросом, попал ли я в крайний случай, когда n^2есть нижняя граница, или же он не может быть понижен до обычного в n log nконце концов - просто проверяю, есть ли ситуации, когда более высокая граница, такая как n^2, уже известна.
Бристоль
На самом деле под фоном я подразумеваю, потому что здесь люди пытаются задавать вопросы исследовательского уровня , поэтому, когда вы предоставляете просто очень наивный подход, это означает, что за этим вопросом не стоит много исследований, возможно, некоторые другие сайты лучше подходят для этого.
Саид
9
Я думаю, что технический термин для того, что вы называете слепой сортировкой, - забывчивая « сеть сортировки » .
Каве

Ответы:

14

Гудрич "Рандомизированная сортировка по Шеллу: простой алгоритм сортировки с забвением " рассматривает сортировку без учета данных. Сортирующие сети не обращают внимания на данные, но, как я понимаю, нецелесообразны.

jbapple
источник
3
Я думаю, что битоническая сортировка не такая непрактичная, но О(Nжурнал2N), Сортировочная сеть AKS определенно нецелесообразна.
Дэвид Эппштейн