Все мы знаем, что минимальная сложность алгоритма сортировки на основе сравнения сравнения. Я пытаюсь сделать слепой сортировку, т.е. с учетом числа вывести схему (с логическими, арифметическими и "сравнительными" вентилями), которая сортирует список Предметы.
Предварительный расчет всех сравнений и последующее выполнение арифметики с полученными битами дает мне алгоритм , однако с помощью какой-то безумной "арифметики с указателями" я думаю, что могу получить версия.
Существует ли известная нижняя граница для схем сортировки на основе сравнения вдоль линий, аналогичных для алгоритма сортировки на основе сравнения? Может ли быть вообще возможна слепая сортировка в раз?
cc.complexity-theory
terminology
sorting
Бристоль
источник
источник
n^2
есть нижняя граница, или же он не может быть понижен до обычного вn log n
конце концов - просто проверяю, есть ли ситуации, когда более высокая граница, такая какn^2
, уже известна.Ответы:
Гудрич "Рандомизированная сортировка по Шеллу: простой алгоритм сортировки с забвением " рассматривает сортировку без учета данных. Сортирующие сети не обращают внимания на данные, но, как я понимаю, нецелесообразны.
источник