Sleep sort

[jayrandom]

И я считаю, что Sleep sort - гениальный алгоритм для сортировки.

Там народ придирается в общем-то к мелочам - "что будет, если я пошлю очень большие числа на сортировку?". Надо просто всё нормализовать в интервал от 0 до 1, это делается за линейное время. Остальная сортировка происходит буквально за секунду

Comments

[chip33]

Хе-хе, забавная идея.

[livelight]

Надеюсь, вы таки шутите.

Хотел сказать, что комментаторы жгут, и разве что на брейнфаке не написали [хоть какой-то] алгоритм - но оказалось, что написали :)

[jayrandom]

В каком месте шучу?

Вообще, конкретная реализация (язык, платформа) - совершенно не важна. Важен принцип взаимопреобразования времени и пространства (памяти), который здесь совершенно шикарно использован.

[livelight]

Вся теория сложности, в рамках которой обычно выводятся оценки вида O(n*log(n)), построена для случая _одного_ вычислителя. Для построения класса алгоритмов NP (известного по NP-полным задачам) вводится специфическое псевдо-распараллеливание с очень ограниченной функциональностью.

В случае, если у нас есть бесконечное количество вычислителей с нулевыми накладными расходами на взаимодействие, вообще всё выглядит по-другому. Например, NP-полная задача взлома хорошего шифра, которая решается путём полного перебора всех возможных ключей (откуда и берётся экспонента по длине ключа) при практически фиксированном времени проверки одного ключа, станет решаться за фиксированное время.

[jayrandom]

;-)

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

[a_p]

вообще-то отсортировать целые числа за О(наибольшее значение + эн) можно, просто построив гистограмму.

[jayrandom]

Правильно, это и есть в некотором роде "гистограмма". Но для хранения гистограммы нужно место (плюс структуры для манипуляции), а тут гистограмма (или процесс её построения) погружён во время.

[a_p]

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

[rapitosov]

идея классная, но во время прохода по аргументам таймер на месте не стоит - есть возможность промахнуться