стабильная сортировка в O (n log (log n))

Question

Для данного массива из N действительных чисел каждое число имеет свой собственный ключ, но ключи не обязательно разные. Известно, что у нас есть k разных ключей.

Мне нужно найти стабильный алгоритм сортировки в O (N log (log N)) сложности при k = O (log N), Я могу использовать дополнительное пространство O (N)?

Я пробовал все, и я ничего не могу придумать.

Answer 1

http://en.wikipedia.org/wiki/Sorting_algorithm утверждает, что алгоритмы Han и Thorup имеют требуемую сложность.

Answer 2

Как указывает Тилман Фогель, существуют алгоритмы, которые теоретически могут выполняться в сложности Θ (n log (log n)), накладывая определенные ограничения на входные данные. Похоже, они вряд ли принесут большую пользу в большинстве практических приложений, и, вероятно, почему я никогда не видел реализации, но если они соответствуют вашему прецеденту, мне было бы очень интересно узнать, быстрее ли эти алгоритмы.

Это отрывок из Алгоритм проектирования Стивен С. Skiena Руководство объяснить, почему это невозможно придумать общего назначения Θ (п журнал (журнал N)) сортировать по алгоритму:

Мы видели несколько алгоритмов сортировки, которые выполняются в наихудшем случае O (n log n), но ни один из них не является линейным. Для сортировки n элементов, конечно, нужно смотреть на них, поэтому любой алгоритм сортировки должен быть Ω (n) в худшем случае. Можем ли мы закрыть этот оставшийся пробег Θ (log n)?

Ответ отрицательный. Нижнюю границу Ω (n log n) можно показать, заметив, что любой алгоритм сортировки должен вести себя по-разному во время исполнения на каждом из отдельных n! перестановки n ключей. Результат каждого попарного сравнения определяет поведение во время выполнения любого алгоритма сортировки на основе сравнения. Мы можем думать о множестве всех возможных исполнений такого алгоритма, как дерево с n! листья. Дерево минимальной высоты соответствует самому быстрому алгоритму, и бывает, что lg (n!) = Θ (n log n).

Answer 3

Для достижения этой границы мы должны думать о деревьях, в частности, о бинарных деревьях поиска. Существует класс двоичных деревьев поиска, у которых есть дополнительная информация в узле, как родитель, левый ребенок, правый ребенок и цвет ... да, я говорю о красных черных деревьях. Сложность времени для вставки одного узла в дерево RB - это O (log n), n - количество узлов дерева. Основная идея - пересечь массив и вставить каждый элемент в дерево RB, но с одним ограничением, если мы обнаружим дублированный элемент, не вставляйте !!!, просто считайте !. Как это сделать? просто добавьте поле «счет» в узел, и каждый раз, когда вы обнаружите дублированный элемент, просто увеличивайте счетчик, но не вставляйте его в качестве нового узла. Для этого в дереве RB будут только элементы O (k), т. Е. O (log n) для нашего примера. Таким образом, сложность вставки одного узла в дерево RB - O (log (log n)). Как только мы вставим все элементы в дерево RB, временной сложностью будет O (n log (log n)). Следующий шаг - пересечь дерево в порядке !! и дублировать каждый элемент таким образом, чтобы счетчик был. Для этого мы имеем отсортированный массив (деревья RB - двоичные деревья поиска), и поскольку сложность времени для перемещения в порядке O (n), общая временная сложность будет равна O (n log (log n)).

Answer 4

Вы, ребята, думаете об «традиционных» алгоритмах сортировки (пузырь, слияние, быстрый и т. Д.), Когда оригинальный алгоритм, который он описал, в основном представляет собой описание BucketSort или RadixSort. Они не подпадают под ограничение Ω (nlogn), так как они не выполняют бинарные сравнения, а сравниваются в соответствии с количеством элементов, подлежащих сортировке!

Я могу только предположить, что форма Radixsort для полилогарифмического числа ключей или значений n элементов, подлежащих сортировке, может иметь желаемую сложность. Однако я не уверен на 100%, поскольку я не тестировал его и не проверял.