ボゾソートとは? わかりやすく解説

ボゴソート

(ボゾソート から転送)

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/06/13 18:33 UTC 版)

ナビゲーションに移動 検索に移動
ボゴソート
クラス ソート
データ構造 配列
最悪計算時間
最良計算時間
平均計算時間
最悪空間計算量

ボゴソート (bogosort) は、ソートアルゴリズムの一つ。平均的な計算時間はO(n×n!)で、非常に効率の悪いアルゴリズムとして知られている。安定ソートではない。「bogo」は、"bogus"[1]に由来する。

英語では、random sort(ランダムソート), shotgun sort(「数撃ちゃ当たる」ソート), monkey sort(「猿でもできる」ソート) などといった表現がある。なお最後のものは「猿でもできる」というよりも、無限の猿定理を指しているかもしれない。

アルゴリズム

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

  1. トランプ52枚の束を放り投げて、ばらばらにする。
  2. 1枚ずつ無作為にすべてを拾い集める。
  3. ソートされているか確認する。もしソート済みでなければ、1から3までの手順を繰り返す。

カードの束をひたすらシャッフルし続けて順番に並ぶまで待つアルゴリズムと考えてもよい。

疑似コード

function bogosort(array)
  while not is_sorted(array)
    array := random_permutation(array)

Perlによる実装

use List::Util 'shuffle';
sub is_sorted {
  for (1 .. $#_) {
    return 0 if ($_[$_ - 1] > $_[$_]);
  }
  return 1;
}
sub bogosort {
  until (is_sorted(@_)) {
    @_ = shuffle @_;
  }
  return @_;
}

C++による実装

#include <algorithm>
#include <random>
template <class RandomIter>
void bogosort( RandomIter first, RandomIter last )
{
  while( !std::is_sorted( first, last ) )
    std::shuffle( first, last, std::default_random_engine() );
}

計算時間および停止性

すべての要素が互いに異なる場合、時間計算量はO(n×n!)となる(1回の並べ直しに必要な操作量が n 、それを繰り返す回数の期待値のオーダーが n! )。n! は、全ての並びのうち、正しい並びである割合である 1 / n! の逆数であり、等しい要素が含まれている場合、それによる正しい並びの個数が a とすると、O(n×n! / a) となる。以上はかなりおおざっぱな議論で、たとえば並びを判定する計算量を考慮していない。

理論的にはまた、このアルゴリズムの停止性は無限の猿定理に依ることになる。なお実際的には、現実のコンピュータで実施した場合、擬似乱数のせいで停止しないこともあり得る。

関連アルゴリズム

ボゾソート

ボゾソートも乱数に基づくソートのアルゴリズムである。リストがソートされていなければ二つの要素をランダムに取り出して入れ替え、リストがソートされているかどうかを調べる。ボゾソートの実行時間の解析は難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithms[2]に実行時間の見積もりが示されている。

その他

ジャーゴンファイルの「bogo-sort」の項[3]では「A spectacular variant」が提案されているとして、「量子的に」全ての選択を並列に行い、正しかったもののみを結果として取り出す、というアイディアが示されている。

関連項目

参考文献

  1. ^ http://catb.org/~esr/jargon/html/B/bogus.html
  2. ^ H. Gruber, M. Holzer and O. Ruepp: Sorting the Slow Way: An Analysis of Perversely Awful Randomized Sorting Algorithms, 4th International Conference on Fun with Algorithms, Castiglioncello, Italy, 2007, Lecture Notes in Computer Science 4475, pp. 183-197.
  3. ^ http://catb.org/~esr/jargon/html/B/bogo-sort.html

ボゾソート

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2019/06/13 18:33 UTC 版)

ボゴソート」の記事における「ボゾソート」の解説

ボゾソートも乱数に基づくソートアルゴリズムである。リストソートされていなければ二つ要素ランダムに取り出して入れ替えリストソートされているかどうか調べる。ボゾソートの実行時間解析難しいが、H. GruberのAn Analysis of Perversely Awful Randomized Sorting Algorithmsに実行時間見積もり示されている。

※この「ボゾソート」の解説は、「ボゴソート」の解説の一部です。
「ボゾソート」を含む「ボゴソート」の記事については、「ボゴソート」の概要を参照ください。

ウィキペディア小見出し辞書の「ボゾソート」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ


英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「ボゾソート」の関連用語

ボゾソートのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



ボゾソートのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのボゴソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのボゴソート (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS