遅いソート

http://bugrammer.hateblo.jp/entry/2014/08/16/014212 ( バブルソートよりも非効率なソートアルゴリズムを探して ―― ストゥージソートとスローソート ) を読んで。

ちゃんと終わるけどもっと遅いソートがあるので書いてみた。

たぶん名前がついていると思うんだけど、調べてないので名称不明。
こういう奴。

def try_all_sort(s)
  s.permutation(s.size){ |x|
    return x if x.each_cons(2).all?{ |a,b| a<=b }
  }
end

typical case では bogo sort と同じオーダー。
bogo sort と違って、worst case は有限。O((N+1)!)だと思う。

で。ベンチマーク。
100要素を1000回なんて宇宙が消滅するまでに終わらないので、試したのはシャッフル済み10要素を10回。

手元で測って、30秒ぐらい。
一方、slowsort だと速すぎて測定不能。
bogo sort だと 54秒だった。まあ運次第だけど。

10要素で30秒なので、15要素なら4ヶ月、20要素なら60万年ぐらいかかる。
コンピュータがやる計算なのに、人間が紙に書いてソートするよりずっと遅い。

■ 8/17 追記

メモリ消費は、上記のソースでは O(N)。だと思う。
100要素1000回に要する時間は、普通の人がパッと読んで分かるような表現ができないぐらい長い。
10の148乗年ぐらい。
概ね、千無量大数倍高速化すると、千無量大数年かかるぐらい。百万倍ぐらいサバ読んでるけどいいでしょ？
メモリ消費は、数キロバイト〜数十キロバイト だと思う。

千無量大数倍高速化というと無理難題のように思うかもしれないけど、普通の sort に書き換えれば、それ以上の高速化を実現できる。