キンサクプログラマー

お金儲けと技術のメモ

毎日アルゴリズム(第5日目)ボゴソート

効率の悪いソートアルゴリズム

クイックソートバブルソートなどが有名なソートアルゴリズムだが、中でも効率の悪いボゴソートをご存知だろうか。効率悪いアルゴリズムという響が新鮮だが、いってしまえばただ単にランダムでソートするだけのアルゴリズムだ。

アルゴリズム

カードをばらまいて適当に集め、順番に並んでたらOK。ただそれだけの単純なアルゴリズム

  1. x=[1,5,20,15,4,51,21]みたいな配列があった場合、ランダムに1枚抽出
  2. 次にまたランダムに1枚抽出
  3. 1~2を繰り返し、x==NULLとなったら、抽出されたxの値が降順(昇順)であるか調べる
  4. ダメなら1~3を繰り返す

実装

rand関数だけだと、ちょっとめんどくさいが、Numpyをつかったら無作為抽出が簡単。
リストのサイズが10を超えてくると収束があやしくなってくる。50とか100になるとなかなか終わらない。

import numpy as np
a=[i for i in range(9)]
x = np.array(a)
while 1:
    y = np.random.permutation(x)
    if np.array_equal(y,x):
        break
    
print(y)

github.com