スリープソートについて考えてみました。値の時間だけsleepすることで並べ替えるものです。値の絶対位置が決まっているので、そこに置くと、結果的にソートできている、という感じですかね。問題は、大きい値だと、sleep時間が長くなることです。

要は、値xのとき、sleep(x)なのですが、xを直接評価しなくても良いです。x<yならばf(x)<f(y)となるような関数(単調増加関数)であれば良いですね。

例えば、f(x)=log(1+x)とすれば、x>0の範囲でf(x)>0(sleep時間は正でないと困る)で、f(0)=0, f(10)≈1, f(100)≈2となります。sleep(f(x))のほうが、必要な時間は少ないでしょう。

さらに、f(x)=x/(1+x)とすれば、0<f(x)<1なので、最大1秒で完了します。

もちろん、実際にはsleepを大量実行するので、その点は考慮しなくてはなりません。(他のブログを見ると、実装上の問題を論じているケースが多いようです)

元の値から、実際にsleepに渡す値に変換する関数は、理論上は単調増加でありさえすれば良いです。しかし、差が非常に小さいと、時間差が少なく、ソートミス(処理時間差の影響が大きくなる)可能性があります。これを回避するには、f(x)=ax/(b+x)として、a, bの値を上手く設定すれば良さそうですが、ソート対象の値をある程度知る必要があるのでは？(クイックソートでピボットの選択を上手くするようなもの？)と思います。この辺はまた次の機会に考えてみたいと思います。

楽天で検索
【楽天ブックスならいつでも送料無料】数学ガール [ 結城浩 ]
1944円
結城浩 SBクリエイティブ発行年月：2007年06月 ページ数：332p サイズ：単行本 ISBN：9784797341379 第1章　数列とパターン／第2章　
楽天ブックス
Supported by 楽天ウェブサービス