概要
- Pythonでソートアルゴリズムを再発明してみるだけ
- 今回はボゴソートについて
- 参考サイトのサンプルコードをできるだけ見ずに実装する
- とりあえず昇順ソートのみの対応とする
ボゴソートの概要
- 配列内の要素をランダムにシャッフルする処理を、偶然ソートされた状態になるまでひたすら繰り返すという狂気のアルゴリズム
- 当然のことながらソートが完了するまで非常に時間がかかり、実用性は全くない
基本的な手順
- 配列内の要素をランダムにシャッフルする
- ソートされた状態になっているかどうかチェック。ソート済みの状態なら終了し、そうでない場合は1に戻る
ソース
import random
from datetime import datetime
def is_sorted(lst):
for i in range(1, len(lst)):
if lst[i-1] > lst[i]:
return False
return True
def bogo_sort(lst):
while True:
random.shuffle(lst)
if is_sorted(lst):
break
lst = list(range(10))
random.shuffle(lst)
print(datetime.now(), end="")
print(" ソート前: " + str(lst))
bogo_sort(lst)
print(datetime.now(), end="")
print(" ソート後: " + str(lst))
どれくらい遅いか見たかったので、適当にタイムスタンプを出すようにしました。
私の手元で試した感じだと速ければ数秒、遅くても1分くらいでした。
要素数が10程度では期待（？）してたほどは遅くないですね。
要素数を増やしたらどうなるか、試したい人は試してください。