これは何？
2014年に 遅いソート という記事を書いた。
もっと遅くできるなと以前から思っていたんだけど、それを記事にした。
遅いソートの例
Wikipedia の ボゴソート に書いてある例、有名なもの、そして私案を挙げる
bubble sort
遅いソートアルゴリズムとして、おそらく最も有名。
def bubblesort!(s)
(s.size).times do |i|
(1...s.size).each do |j|
s[j], s[j-1] = s[j-1], s[j] if s[j]<s[j-1]
end
end
s
end
一般的には実用にならないぐらい遅いソートアルゴリズムの代表のような扱いだけれど、今回扱うアルゴリズムの中ではぶっちぎりに速い。1000件の整列が瞬きする間に終わるなんて、夢のようだ。
slow sort
Wikipedia に 記事 がある。
- 領域を前半と後半に分ける。
- 前半と後半をそれぞれ slow sort。
- 前半の末尾と後半の末尾を、必要なら入れ替える → 末尾が最大値となることが保証される。
- 末尾を除いた領域を slow sort。
というもの。末尾再帰でなければスタックをたくさん使うが、スタック・オーバーフローするようなデータ量だと計算が終わらないので問題にならないと思う。
ruby で書くとこんな感じ。
def slowsort!(s)
impl = ->(i,j){
return if j<=i
m=(i+j)/2
impl[i,m]
impl[m+1,j]
s[j],s[m] = s[m],s[j] if s[j]<s[m]
impl[i,j-1]
}
impl[0,s.size-1]
s
end
わりとひどいアルゴリズムに見えるけど、今回扱うアルゴリズムでは二番目に速い。
bogo sort
非実用的な遅いソートアルゴリズムとして、おそらく最も有名。
「適当に混ぜて、整列されていたら終了」というシンプルなアイディア。
ruby の場合とても簡単に書ける。
def bogosort(x)
loop do
s = x.shuffle
return s if s.each_cons(2).all?{ |a,b| a<=b }
end
end
乱数の質によっては整列できない（つまり、無限ループとなる）可能性がある。
ワーストケースは無限。
bozo sort
「整列していなければ、ランダムな2要素を入れ替える」を繰り返すだけというこちらもシンプルなアイディア。
こちらは C 言語などでも簡単に書けると思うけど、下記は ruby。
def bozosort!(x)
loop do
return s if s.each_cons(2).all?{ |a,b| a<=b }
a,b = rand(x.size), rand(x.size)
s[a], s[b] = s[b], s[a]
end
end
bogo sort と同じく、乱数の質によっては整列できない（つまり、無限ループとなる）可能性がある。
直感的には bogo sort より遅そうだけど、動かしてみるとわりと同じぐらいに見える。
拙作(2014)
2014年に私が考えた計算。
もっと前に誰かが考えていると思うけど、探してないので私より先に発見した人がいるかどうかは知らない。
並べ方を全部列挙して、整列済みならそれを返すというもの。
bogo sort と似ているけど、 bogo sort と違って有限の時間で終わる。
ruby で書くと簡単。
def nabesort_2014(s)
s.permutation(s.size){ |x|
return x if x.each_cons(2).all?{ |a,b| a<=b }
}
end
平均的な計算時間は bogo sort と同じだと思う。
拙作(2022)
2014年の記事を書いた後、 repeated_permutation にしたらもっと遅くなるよね、と誰かに言われたのか自分で気づいたのか覚えてない。
で、書いた。
def nabesort_2022(s)
s.repeated_permutation(s.size){ |x|
return x if (
x.each_cons(2).all?{ |a,b| a<=b } &&
x.all?{ |e| x.count(e)==s.count(e) }
)
}
end
終了条件として、できた列が整列済みか否かの他に、各要素の個数が入力の列と同じかどうもチェックする必要がある。
そのチェックに 最悪 $O(n^2)$ の計算を入れている。
もっと遅くすることはできるんだと思うけど、今回紹介する中では一番遅い。
オーダー
真剣に検討してないけど、下表ぐらいだと思う。
| 名前 | typical case | best case | worst case | n=100 |
|---|---|---|---|---|
| bubble | $O(n^2)$ | 同左 | 同左 | $10^4$ |
| slow | $O(exp(6n^{1/6}))$ ぐらいかな | 同左 | 同左 | $10^6$ |
| bogo | $O(n!)$ ぐらい | $O(n)$ | $O(∞)$ | $10^{160}$ |
| bozo | $O(n!)$ ぐらいかな | $O(n)$ | $O(∞)$ | $10^{160}$ |
| 鍋2014 | $O(n!)$ ぐらい | $O(n)$ ぐらい | $O(n!)$ ぐらい | $10^{160}$ |
| 鍋2020 | $O(n^n)$ ぐらい | $O(n^2)$ ぐらい | $O(n^n)$ ぐらい | $10^{200}$ |
たとえば。「$O(n^n)$ ぐらい」は、適当なあまりおおきくない定数 A があれば「$O(n^n)$」と「$O((n+A)^{n+A})$」の間のどこかじゃないかな、ぐらいの気持ち。
slow のオーダーはよくわからないんだけど、雑にフィットしてこれぐらい。
bozo もよくわからないんだけど、bogo と同じぐらいかなと思っている。
実測
シャッフル済みの要素数 9 の配列を 1回だけ整列するという、かなりしょぼい計算をした。
最初、要素数 10 にしたんだけど、10分たっても終わらなかったので 9 にした。
user system total real
bubble 0.000012 0.000000 0.000012 ( 0.000011)
slow 0.000019 0.000001 0.000020 ( 0.000020)
bogo 1.092641 0.006429 1.099070 ( 1.099211)
bozo 1.069077 0.004266 1.073343 ( 1.073448)
nabe 2014 0.178649 0.001577 0.180226 ( 0.180302)
nabe 2022 185.339007 1.285942 186.624949 (186.634422)
nabe 2022 だと、9要素の整列に3分以上を要した模様。人間のほうが速い。
この調子だと、10要素は40分ぐらいかな。
まとめ
軽い気持ちで書いてみたら、思ったよりだいぶ遅くなった。
あと、Wikipedia の bogosort のページ に、Worstsort というもっと遅そうなのがあったけど、試せないほど遅そうなので試してない。
それと。
もし、もっと遅いアルゴリズムがあるという場合は、この記事のコメント欄でそのアルゴリズムを紹介するのではなく、別の記事を起こすことをおすすめする。