コンテンツにスキップ

ボゴソート

出典: へっぽこ実験ウィキ『八百科事典(トンチンペディア)』
順番は、待っていれば向こうから来る。
〜 ボゴソート について、トランプの束

ボゴソート(英: bogosort)は、並べ替えたいものを無作為に混ぜ、並んでいるか確かめ、並んでいなければまた混ぜる整列アルゴリズムである。名前は英語の「bogus(いんちきの)」から来ており、ほかに「愚か者のソート」「猿のソート」「順列ソート」とも呼ばれる。実在するアルゴリズムで、計算機科学の教科書では、やってはいけないことの見本として丁寧に紹介される。

この記事も、ボゴソートで整えている途中である。節には1から5までの番号が振ってあるが、いまは4, 2, 5, 1, 3の順に並んでいる。5つの節の並べ方は120通りあるので、編集のたびに節を無作為に混ぜ直すと、正しい順に並ぶまでの編集回数の期待値は120回になる。これまでの編集は37回である。読者は好きな順に読んでかまわないが、それはボゴソートではなく、ただの読書である。

4. 量子ボゴソート

[いじくる | はらわた]

量子ボゴソートは、量子的な乱数で一度だけ混ぜ、並んでいなければその宇宙を破壊する改良版である。多世界解釈が正しければ、破壊を免れた宇宙では必ず並んでいるので、手間はnに比例するだけで済む。宇宙の破壊のしかたについては、どの文献も書いていない。

この記事は量子ボゴソートを使っていない。もし使っていたなら、あなたが読んでいるこの宇宙では、節は1から順に並んでいるはずである。並んでいないので、この宇宙は量子ボゴソートと関係のない宇宙であることが分かる。念のため、ほかの宇宙のこの記事に問い合わせを出したが、返事は来ていない。

手順は次の3つで、手順の番号もボゴソートで混ぜてある。

  • 3. 並んでいなければ、1に戻る。
  • 1. 混ぜる。
  • 2. 並んでいるか確かめる。

実行する人は番号どおりに実行するので、手順が混ざっていても困ることは無い。ただし、最初にどの番号から始めるかは手順のどこにも書かれていないため、手順そのものを先にボゴソートで並べる必要がある。手順を並べる手順は、上の3つである。

5. 現在の並び

[いじくる | はらわた]

下の欄には、この記事の節の並びの候補が一つ表示される。ページを読み込み直すたびに混ざる。

1, 2, 3, 4, 5 ― 並んだ。ただし、この欄は本文と配線されていない。

候補は5つしか用意していない。120通りすべてを書くと、この節がほかの4つの節を合わせたより長くなり、節を長さの順に並べたほうが早く片づいてしまうからである。5つの候補のうち並んでいるものは1つなので、この欄に限っては平均5回で並ぶ。この記事でいちばん速い部分である。

1. 計算量

[いじくる | はらわた]
撮影の直前まで、このトランプは並んでいた。

ボゴソートの速さは運で決まる。最良の場合、最初から並んでいるものを1回確かめて終わるので、知られているどの整列アルゴリズムよりも速い。何も並べ替えていないからである。平均では、n個のものを並べるのにn!回ほど混ぜ、そのたびにn−1回ほど比べるので、手間はおよそn×n!に比例する。最悪の場合には終わらない。

並べる数 混ぜる回数の期待値 1秒に1回混ぜたとき
3 6回 6秒
5 120回 2分
10 3,628,800回 約42日
13 6,227,020,800回 約197年
52(トランプ1組) 約8.07×1067回 宇宙の年齢の約2×1050倍

13個のときの197年は、鉛筆1本を一人の人間が削らずに使い切るまでの年数とちょうど同じである[要出典]。52枚のトランプを1秒に1回混ぜ続けた場合、最初に並ぶまでに宇宙は何度でも終わるが、トランプは終わらないので、確かめる係だけは毎回新しく探さなければならない。

ボゴソートには、似た考えのアルゴリズムがいくつかある。ボゾソートは、全体を混ぜる代わりに、無作為に選んだ2つを入れ替えては確かめる。少しずつしか混ぜないので、少しずつしか並ばない。

ゴロソートは、2011年のプログラミングの大会「Google Code Jam」の予選に出された問題に出てくる。ゴロという人物が、並べたい数の一部を手で押さえ、机を叩いて残りを跳ね上がらせ、落ちてきた並びを確かめる。問題文によれば、ゴロには腕が4本ある。問われたのは叩く回数の期待値で、腕の本数は答えに関係しなかった。

ボゴソートの家系図を作る試みもあった。ボゴソート、ボゾソート、ゴロソートを紙に並べたところ、どれが親でどれが子かを確かめる手段が無かったので、家系図を混ぜて、親子らしく並ぶまで待つことにした。家系図はいま、37回目である。

関連項目

[いじくる | はらわた]
Cookieは私達のサービスを提供するのに役立ちます。このサービスを使用することにより、お客様はCookieの使用に同意するものとします。