ボゴソートを使用する

ボゴソート (bogo sort, permutation sort) は、配列をランダムに並べ替え、昇順になったら終了するまで繰り返す整列アルゴリズムとして知られる。

「ボゴ (bogo)」は「ボンゴ (bongo)」の略で、乱暴に並べ替える様子を表す造語とされる。意図的に非効率なジョークアルゴリズムの代表例である。

  1. 整列判定: 配列 A が昇順かどうかを調べる。整っていれば終了する。
  2. シャッフル: 整っていなければ、A の要素をランダムに並べ替える。
  3. 繰り返し: 手順 1 に戻る。
procedure bogo_sort(A)
  while not is_sorted(A) do
    shuffle(A)
  return A

各試行で n! 通りの並びのうち 1 つだけが正解であるため、期待試行回数は O(n!) 程度になる。1 回の整列判定に O(n)、シャッフルにも O(n) かかるので、期待時間はおおむね O(n · n!) である。

最悪では正解の並びがなかなか現れず、試行回数に上限を設けない限り終了時刻は保証できない。

類似アルゴリズムとの相違点

スリープソートやスローソートも実用を想定しない整列法だが、 ボゴソートは比較や再帰による整え直しではなく、完全なランダム並べ替えに頼る点が特徴的である。

ストゥージソートは決定的な再帰手順で意図的に遅くするのに対し、 ボゴソートは非決定的で、同じ入力でも試行回数が実行のたびに大きく変わる。