経緯
アルゴリズムの勉強をしていたら奇妙なソートに出会った。
ソートしてるのかも怪しい。。
ボゴソート（bogo sort）とは
ソートのアルゴリズムの一つ。
非常に効率の悪いアルゴリズムとして知られている。
In computer science, bogosort(also known as permutation sort, stupid sort, or slowsort) is a sorting algorithm based on the generate and test paradigm.
（コンピュータ サイエンスでは、bogosort (順列ソート、愚かなソート、またはスローソートとも呼ばれます) は、生成とテストのパラダイムに基づくソートアルゴリズムです。）
この「ボゴ」は、英語の bogus から来ていて、「偽物」「でっち上げ」 って意味があるらしい。
どんだけポンコツなんだろ。
なぜ英語wikiなのかというと、このボゴソートには2種類のバージョンがあるらしい。
- randomized version（ランダム化された）
- deterministic version（決定論的）
日本語版では randomized の方が紹介されているので本記事もそっちで扱います。
効率の良いソートとしてはクイックソートなどが知られてるけど、
最も効率の悪いソートが 「ボゴソート」 なんだね。
アルゴリズム
トランプを例にすると、
- トランプ52枚の束を放り投げて、バラバラにする。
- 1枚ずつ無作為にすべてを拾い集める。
- ソートされているか確認する。
- 1から3までの手順を繰り返す。
らしい。これはもうアルゴリズムなのか。。？
無作為ってところが抽象的で、コードに起こすときはrandomモジュールを使うことで無作為を表現しようと思います
実装してみる
import random
# ソートされているかどうか
def isSorted(nums):
for i in range(len(nums) - 1):
if nums[i] > nums[i + 1]:
return False
return True
# ソートされるまで無限にシャッフルする
def bogoSort(nums):
cnt = 0
while not isSorted(nums):
random.shuffle(nums)
cnt += 1
return cnt
def main():
# 範囲1~10まで、長さ10の配列を作る（重複無し）
nums = random.sample(range(10), k=10)
cnt = bogoSort(nums)
print(str(cnt) + " times shuffled.")
if __name__ == "__main__":
main()
コードはすっきり書けますね。
random モジュールの sample で適当な配列を作り、shuffleで混ぜてます。
予想
10個くらいなら、1万回もループすれば終わりそう。
3秒くらいとみた！
実行してみる
環境
| System | Version |
|---|---|
| OS | MacOS Monterey(12.1) |
| python | 3.8.8 |
| bash | GNU bash, version 3.2.57(1)-release |
| zsh | zsh 5.8 (x86_64-apple-darwin21.0) |
前提条件
| 項目 | 条件 |
|---|---|
| 範囲(int) | 0 ~ 10 |
| 要素数(n) | 10 |
| 重複 | 無し |
time python bogosort.py
11450 times shuffled.
python bogosort.py 0.10s user 0.04s system 52% cpu 0.265 total
0.10s
あれ？意外と早いんじゃね？
再度実行
2289936 times shuffled.
python bogosort.py 10.33s user 0.04s system 97% cpu 10.685 total
10.33s
なんだ、たまたまか。
何回か試してみるためスクリプトを作ってみた。
touch log.txt
for i in `seq 5`
do
echo "<$i回目>" >> log.txt
(time python bogosort.py) 2>&1 | tee -a log.txt
echo "" >> log.txt
done
（timeコマンドは標準エラー出力だったことを知り、ファイルのリダイレクトがうまくいかず苦戦したのも良い勉強になった。。）
zsh keisoku.sh
<1回目>
1528975 times shuffled.
python bogosort.py 8.59s user 0.12s system 92% cpu 9.421 total
<2回目>
849286 times shuffled.
python bogosort.py 4.72s user 0.04s system 98% cpu 4.840 total
<3回目>
3672885 times shuffled.
python bogosort.py 21.86s user 0.23s system 88% cpu 24.878 total
<4回目>
180921 times shuffled.
python bogosort.py 1.46s user 0.04s system 73% cpu 2.037 total
<5回目>
9826624 times shuffled.
python bogosort.py 63.35s user 0.59s system 89% cpu 1:11.69 total
ふむふむ、使えねぇソートだ。
計算量（オーダー）
| 最悪計算時間 | 最良計算時間 | 平均計算時間 |
|---|---|---|
| $O(∞)$ | $O(n)$ | $O(n*n!)$ or $O((n+1)!)$ |
平均計算時間の表記がいろんなサイトで違う書き方されてる。
条件によって異なるってことかな。
終わりに
ボゴソートを別言語で実装した人もいますね。
従来のソートアルゴリズムの凄さを実感したってことにする。
今回は10個で試しましたが、それより多い数は言うまでもないです。
補足
「keisoku.sh」ファイルを実行するときに、bash keisoku.shとしてもよかったんだけど、なぜか文字化けしたのでzshで実行してました。
bashとzshとで変数の展開の仕方が違うからかな？とか考えてた。
変数の語尾に日本語がある場合は文字化けしてしまうため、ドル波括弧${t}で記述する必要ある。
なるほど、書き方が違うのか。
でも文字化けする根本的な原因はイマイチわかってない。。
次回はこれも調べてみようかな。
参考にしたサイト