読者です 読者をやめる 読者になる 読者になる

日常

ケ・セラ・セラ

最弱ソートアルゴリズム、ボゴソート

algorithm

より良いアルゴリズムを求めることはある。より悪いアルゴリズムというのは特に考えたことがなかった。

たまたま、ソートアルゴリズム最弱っぽいものを知っておもしろかった。ボゴソート (bogosort) というらしい。

そのアルゴリズムはこんな感じ。平均的な計算時間はO(n×n!)で、安定ソートではない。

トランプを順に並べる場合を例にすると、次のようになる。

  1. トランプ52枚の束を放り投げて、ばらばらにする。

  2. 1枚ずつ無作為にすべてを拾い集める。

  3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。