遅いソート - 鍋あり谷あり

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回なんて宇宙が消滅するまでに終わらないので、試した

[Nabetani]

セルクマ

[cider_kondo]

四天王を倒したと思ったらベルゼバブのいる魔龍城の扉が開かれたでござるの巻。桁違いとかそんなチンケな言葉ではこのソートの恐ろしさは表現できない

[nisemono_san]

すごい、世界は広い

[rryu]

並べ替えるのではなく整列された状態を探し出すという発想の転換がすごい。

[igrep]

なるほど！

[Kakesoba]

“2008”

[lombriz]

とりあえず、permutationをrepeated permutationに変えて要素が揃ってることの検査を入れれば、O(n^n)まで遅くできるかな？

[mumincacao]

どれが正解かわかんないなら全部列挙しちゃえばいいじゃないそーと？（・ω・；【みかん

[ad2217]

これは正当な遅さだ。もっと遅くするには、permutationの代わりに激しく重複があるが最終的には全部の組み合わせを出力するようなものを考えればよい気がする。bogo sort より遅くなるか。

[knjname]

ソート対象配列の全並び替え例を作成し、そのうちソートされているものを選ぶソート。消費メモリサイズはpermutationが決定かな。