読者です 読者をやめる 読者になる 読者になる

どせいたんさき。

ナスダヨー

比較しないソートアルゴリズム ― sleep sort

twitterから流れてきて面白かったのでメモ.元ネタは 4chan.org のここらしい.


最大値を探すのも最小値を探すのも O(n) でできる(?)から sleep の時間を規格化するには O(n) でできるはず.となれば大変理想的な状況を想定すると O(n) でソートできるのでしょうか.togetter での反応を読んで知りましたが bin sort とか bucket sort と呼ばれるものの派生(メモリ空間を時間軸に!)と考えられるそうです.発想はもちろん本家 >>1 の実装が大変シンプルでとても面白いです.これ思いついて掲示板に書きこんだときの >>1 は興奮していただろうなあと思わざるを得ません.