bogo-sort

/boh`goh·sort´/, 名詞

(異形:stupid-sort)あまのじゃくにひどいアルゴリズムの典型(単に一般的に悪いアルゴリズムにすぎないbubble sortとは対照的)。bogo-sortは、トランプ一組を繰り返し宙に放り投げ、無作為に拾い上げ、それから順番どおりかどうかを調べるのに等しい。ひどさの一種の規範的な例として役立つ。プログラムを見て、まぬけなアルゴリズムを見つけたとき、「ああ、なるほど、このプログラムはbogo-sortを使っているな」と言うかもしれない。平均の場合に階乗時間や超指数時間で動き、最悪の場合の実行時間が確率的に無限になるアルゴリズムに特にふさわしい。bogus、brute forceと比較せよ。

量子力学の多世界解釈が真であるなら、任意の大きさの配列を線形時間でソートできる、という興味深い性質を持つ、bogo-sortの華々しい変種が提案されている。(多世界モデルでは、あらゆる量子的作用の結果は、ソート前の宇宙を、状態ベクトルが収縮しうる各々の仕方ごとに一つずつ、ソート後の宇宙の束へと分裂させる。ソート後のどの一つの宇宙でも結果は無作為に見える。)手順は次のとおり。1. 量子過程を使って配列を無作為に並べ替える。2. 配列がソートされていなければ、宇宙を破壊する(リストがソートされているか確認するにはO(n)時間が要る)。手順2の実装は読者への演習として残しておく。