アニヲタWiki(仮)

登録日：2019/08/13 Tue 23:30:32
更新日：2023/07/07 Fri 09:34:36
所要時間：約 6 分で読めます

▽タグ一覧
TASさん専用 アルゴリズム ソート ボゴソート 数撃ちゃ当たる 欠陥品←可能性自体はある 複雑 適当にやってりゃいつかは終わる←乱数の取り方によっては……

突然だが、この項目を見ているwiki篭り諸君は「ソート」というものをご存知だろうか？

分かりやすく言えばランダムに並べられたデータの集合を順番どおりに並べ替えるアルゴリズムの一つで、アルゴリズムの入門書などでは比較的早い段階で出る事が多い。
ボゴソートはその一種である。詳細について説明する前にまずアルゴリズムに関連する簡単な用語についてざっくりと説明しよう。

①：計算量
簡単に言えばデータの集合に適用するアルゴリズムが始まってから終わるまでの計算の回数のこと。
基本的にアルゴリズムはコンピュータに対してプログラムと集合を準備し実装していくのだが、使用するコンピュータのメモリ等の関係上、計算量が多いとアルゴリズムを最後まで行えるか、行えるならどのくらいかかるかという問題が出てくる。
つまり計算量が小さいほどそのアルゴリズムは早く終わる事になる。

計算量と一口に行っても公式の様にガッチリ決まっているわけではないので、平均的にはどのくらいになるのかを考える「平均計算量」、これ以上遅くなる事はないという指標である「最悪計算量」、逆に理想的なパターンを表す「最良計算量」などの様々なパターンが考えられている。

②：ランダウ記号
データの集合がn個の要素を持っていたとする。
その集合に対してアルゴリズムによる特定の処理を行う場合、計算量は基本的にnの値に影響される。
つまり計算量はnの関数で表現できるという事である。しかしその式が簡単とは限らない。

そこで役に立つのがランダウ記号である。簡単な定義を書くと「出てきたnの式P(n)が、nが十分大きい所では関数f(n)の定数倍より小さくなる時、P(n)＝O(f(n))とする(*1)。」となる。
この定義では「なんのこっちゃ？」と思う人もいるかもしれないが、これに関しては「なるべく簡単な関数でnの式を大雑把に表現しちゃおう！」程度の認識で良い。
なお上の定義ではf(n)は条件さえ満たしていればいくらでも大きくしていいのだが、基本的には出来るだけ小さな関数を用いるのが通例である。

さて、これらを踏まえてボゴソートに戻る。
先ほど述べた通りソートは「与えられたデータの整序」が目的のアルゴリズムなのだがボゴソートの手順はと言うと……、

①：与えられたn個のデータをバラバラにして、その後無作為に並べる。
②：①で並べたデータの列が正しい並びになっていれば終了する。なっていなかった場合①に戻る。

なぁにこれぇ。

そう、このボゴソート、あまりにもいい加減すぎるアルゴリズムなのだ。

トランプ等のカードゲームで例えるなら、

①：山札をシャッフルする。当然積み込みはなし。
②：シャッフルしたカードを見てカード名があらかじめ決めておいた順番どおりに並んでいればソート完了。違っていればまたシャッフルをする。

名前もなかなか辛辣で「ボゴ」はbogus(インチキ・偽物)から来ており、monkey sort(猿でもできるソート)やshotgun sort(数撃ちゃあたるソート)などの変な別名もある。
通常、ソートを大雑把に分けると「実装は簡単だが時間のかかるソート」と「実装に多少手間がかかるが時間のかからないソート」に分かれる。
例を挙げると……

バブルソート
①：並べたn個のデータを左端から2つずつ見ていく。
②：2つのデータの並びが反対ならば入れ替え、そうでなければそのまま。
③：②の作業がデータの右端まで来たとき、並びが正しいならソート完了、違っていた場合、もう一度左端から見ていく。

クイックソート
①：n個のデータを並べた際に基準となる値を持つデータ(「ピボット」と言う。)を1つ選択する。
②：ピボットの位置を基準にそれより大きいものと小さいもののグループにデータを分割する。
③：分けたグループ内で簡単に実装できるソートを行う。

バブルソートは非常に実装が簡単だが、その分時間はかなりかかるソート、クイックソートは実装は多少面倒(*2)だが、計算時間は速いソートである。

n個のデータに対する計算時間について書くと……

平均計算時間：バブルソート…O(n^2)、クイックソート…O(n log n)
最良計算時間：バブルソート…O(n)、クイックソート…O(n log n)
最悪計算時間：バブルソート…O(n^2)、クイックソート…O(n^2)

となる。(log nはe(「自然対数の底」と言う数)がnと等しくなる為に必要な累乗の数を指す。)

パッと見ても分かりにくいかもしれないが、log n(対数関数)は増加が途轍もなく遅い関数なので、nが大きいとこの関数の影響が大きくはたらいてくる。

と、ここまでは一般的なソートの話。
このボゴソートの場合の計算時間は以下の通り。

平均計算時間： O(n×n!)(*3)
最良計算時間： O(n)
最悪計算時間： O(∞)

…うん、分かる人には分かるだろう。ものすごく遅い。

平均計算量の理屈としては「1回の並べ替え」にn回の操作、繰り返しの回数が期待値n!だけ行われるためにそのかけあわせでこのような値になる事になる事から決定する。

とは言え、これだけだとよく分からないかもしれないので、各ソートの平均計算量のランダウ記号の中の関数の値(*4)を見てみると・・・

n=5
n^2(バブルソート) → 25
n log n(クイックソート) → 8(*5)
n×n!(ボゴソート) → 600

n=10
n^2(バブルソート) → 100
n log n(クイックソート) → 23
n×n!(ボゴソート) → 36288000

n=15
n^2(バブルソート) → 225
n log n(クイックソート) → 41
n×n!(ボゴソート) → 19615115520000

これ以上は止めておくが、nの増加でボゴソートの計算量が爆発的に増加している。
nの数が膨大になれば計算量が大きくなりすぎて、容量内での計算が極めて困難、あるいは不可能になってしまうこともあり得る。

こんなボゴソートだが、実は理論上有限回で終わる事が保証されている。
これは「無限の猿定理」という、「ランダムな文字の列を無限に長く作り続ければ、その中にどんな文字列も作れる」と言う定理による。

……が、あくまで「理論上」である。
というのもこのアルゴリズム、一見ランダムに並べて一致しているかどうかを調べるだけなので実装は簡単そうに見えるが、この「ランダム」という点が曲者で、並べ替えの為の乱数をうまく発生させる必要があるので実際にはあまり簡単ではない。
この乱数生成についてだが、完全な乱数ではなく一見乱数に見えるが、実は数を決められた計算によってはじき出している「擬似乱数」というものを使う。上のシャッフルの例で言うならヒンドゥーシャッフルやディールシャッフル、ショット・ガン・シャッフルリフルシャッフルなどの方法の事と思えばいい。
これの作り方によってはランダム性が低く、計算がいつまでも終わらないという事態もあり得るからである。

また有限回と言っているだけでその値が計算機には扱えないレベルの途轍もなく大きい数になる可能性もある。
例えばそれは無量大数の様な数かもしれないし、10の100乗である1グーゴルかもしれない。
はたまた指数表記すらできないほどの巨大数であるグラハム数かもしれないし、それ以上かもしれない。
こうなった場合、計算をするコンピューターはひとたまりもない。

「理論上有限回で止まる」ことと、「有効なアルゴリズムである」こととの間には大きな隔たりがあるのだ。

こういった問題点を持つボゴソートだが、他のソートには見られない特徴として「並び替え後のデータの列が並び替え前のデータの列の状態に全く依存していない」という点が挙げられる。

基本的にソートは並び替えの前後の状態に関係があり、並び替え前の時点で整序がどの程度完成してるかが結果にも影響してくる。(詳しくは触れないが「ソート自体が安定かそうでないか」も関係してくる。)

が、ボゴソートにはそういったものがない為、運がよければ1回目の並び替えであっという間に終わってしまうという事もあり得る。
勿論データ数が増えてしまうと、それも容易ではなくなるのだが、この点も乱数の生成方法によっては上手く行きやすくなる。

変な性質を持つボゴソートだが、乱数の作り方次第では非常にいいソートとなりうるという可能性を秘めたソートでもあるのだ。

追記・修正は全文をランダムに並べ替えて整序が住んでいるか確認しながらお願いします。