ボゾソートで配列を並び替える

ボゾソートを使用する

ボゾソート (bozo sort) は、配列が昇順かどうかを調べ、整っていなければ任意の 2 要素をランダムに選んで入れ替える手順を、昇順になるまで繰り返す整列アルゴリズムである。

「ボゾ (bozo)」は英語の俗語で道化師・間抜けな人を指す語であり、無茶苦茶な並べ替えを表した造語とされる。ボゴソートと同様、意図的に非効率なジョークアルゴリズムの一種である。

1. 整列判定: 配列 A が昇順かどうかを調べる。整っていれば終了する。
2. ランダム交換: 整っていなければ、添字 i と j を（同じ添字もありうる）ランダムに選び、A[i] と A[j] を入れ替える。
3. 繰り返し: 手順 1 に戻る。

procedure bozo_sort(A)
  while not is_sorted(A) do
    i = random integer in [0, length(A) - 1]
    j = random integer in [0, length(A) - 1]
    swap(A[i], A[j])
  return A

ボゴソートが毎回配列全体をランダムに並べ替えるのに対し、ボゾソートは 1 回の試行で 2 要素だけを入れ替える。 それでも正しい並びに到達するまでの試行回数は期待値 O(n!) 程度と見積もられ、1 回の整列判定と交換に O(n) かかるので、期待時間はおおむね O(n · n!) である。

最悪ではずっと不運な交換が続き、試行回数に上限を設けない限り終了時刻は保証できない。

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

ボゴソートは 1 試行ごとに n! 通りの並びのうち 1 つを一様に選ぶが、 ボゾソートは 2 要素の入れ替えだけで隣接する並びへしか遷移しない。どちらも非決定的で、同じ入力でも試行回数が実行のたびに大きく変わる。

ストゥージソートやスローソートは決定的な再帰手順で意図的に遅くするのに対し、 ボゾソートはランダムな交換に頼る点が特徴的である。