ボゴソート
なぜか研究室でボゴソートについて盛り上がったので、そのノリで作ってみた。
matacatさんの作品をforkさせてもらいました。
・ボゴソートとは?
ボゴソート (英語: bogosort) は、ソートのアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。
ボゴソートは、「量子ボゴダイナミックス」というユーモラスな用語にちなんで名付けられている。その元は、bogus(偽の)である。英語では、 random sort, shotgun sort, monkey sort ともいう。
アルゴリズム
トランプを順に並べる場合を例にすると、次のようになる。
1. トランプ52枚の束を放り投げて、ばらばらにする。
2. 1枚ずつ無作為にすべてを拾い集める。
3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。
カードをシャッフルし続けて、偶然一列に並ぶのをひたすら待ちつづけるアルゴリズムと考えてもよい。
運が良ければ一発でソート終了!なんというアルゴリズム!!
熱い!熱過ぎる!!そして馬鹿過ぎる!!!
けど、こういうのも楽しいよね!