突如Twitterでボゴソートの話題が出ていた。最近競プロ熱が再燃しているからか何故か実装したくなった。

ボゴソートは毎回配列をシャッフルしてソートされているかを調べるソートアルゴリズムで、ボゾソートはランダムに2つの値を入れ替えるようなソートアルゴリズムである。
どちらもソートアルゴリズムかすら怪しいようなソートアルゴリズムであり、ネタ枠として有名であると思う。

１. 乱数の生成

それじゃあ、こいつらをC++で実装してみようということでコードを書いていったが、こいつらには乱数がいる。乱数なんて何年ぶりに実装したんだよと。とゆうことで、つぎのような乱数生成器を実装する。

std::random_device rnd;
mt19937 engine(rnd());

これで、engine()とすればかなり精度の良い乱数が生成される。
使うときはrondomをincludeしなければいけない。

random_device rnd で非決定論的な乱数生成器rndが作られ、rndをシード値としてメルセンヌ・ツイスター法による乱数生成器engineが作られる。
random_device は予測不可能な(次に来る数字がわからない)乱数を作るが、遅いので今回はシード値として用いている。

２. ボゴソートの実装

乱数の生成もできたことだし、それではボゴソートを実装しよう。

#include<bits/stdc++.h>
#define M 100 //0~99までの範囲で乱数を生成
using namespace std;

bool correct(int n , vector<int> v)
{
   int k=0;
   for(int i=0;i<n-1;i++)
       if(v[i]<=v[i+1])
           k++;
   if(k==n-1) return true;
   return false;
}

int main()
{
 random_device rnd; //乱数生成器
 mt19937 engine(rnd());
 int n; //配列の個数
 vector <int> bogo;
 cin >> n;
 for(int i=0;i<n;i++)
     bogo.push_back(engine()%M);
 
 //bogosort
 for(;;){
     shuffle(bogo.begin(), bogo.end(), engine);
     if(correct(n, bogo)==true) break;
 }
 
 //出力
 for(int x: bogo )
     cout << x << " ";
 cout << endl;
 return 0;
}

新たにshuffle関数が出たが、algotithmをincludeすれば使うことができる。

３. ボゾソート

//bozosort
for(;;)
    int b = engine() % n, c = engine() % n; //入れ替える配列決め
    for (;;) { //b=cの場合に値を変える
     if (b != c) break;
     b = engine() % n;
     c = engine() % n;
     }
    swap(bozo[b], bozo[c]);
    if(correct(n, bozo)==true) break;
}

ボゴソートの部分とvectorの名前をbogoからbozoに変えたら動く(はず)。
b=cの時に再び乱数で決定しているため計算速度が落ちているので(ボゾソートなのでほぼ関係ないだろ)、工夫したらもっと早くなるけど面倒だからやめた。

４. ボゾソートの効率化

それでは、このクソみたいな計算量のボゾソートをもう少し計算量を落としていこう。

まず思いついたものが、入れ替えた後の方がよりソートされているかを調べて、入れ替えた後の方がソートされていた場合に入れ替えて、ソートされていなかった場合は入れ替えないということである。

しかし、ソートされている配列と比較となると本末転倒になるので別の方法を考える。

それではbozo[i]<=bozo[i+1]となるiの個数で考えてみたらどうだろうか。増えていたら入れ替えて、それ以外ならばそのままにするという感じで。

これで効率化できた(と思うが)比較の個数が多い気がする。nの大きさがそれほど大きくはできないが、何万回もループしていると誤差も大きくなってしまう。

それでは、入れ替えるbozo[i]とbozo[j]の大小を考えてみよう。入れ替えた後にbozo[i]かbozo[j]のいずれか小さいほうが前に来たら、(さっきとは別の方法ではあるが)よりソートされていると考えることができると思う。

これなら1,2回の比較で済みだいぶ効率化されたと思う。ということで実装してみる。

//new bozosort
for(;;){
    int b = engine() % n, c = engine() % n; //入れ替える配列決め
    for (;;) { //b=cの場合に値を変える
        if (b != c) break;
        b = engine() % n;
        c = engine() % n;
    }
    
    if(b>c) swap(b,c); //b<cとなるようにする
    if (n_bozo[b]>=n_bozo[c]) //小さいほうを前にする
        swap(n_bozo[b], n_bozo[c]);
    if(correct(n, n_bozo)==true) break;
}

少し書く量が増えたがこれで効率化されたと思う。

実際それぞれのループ回数(計算回数ではない)をn=6を1000回繰り返した平均と分散は、

bogosort : ave=647.766 s^2=512567
bozosort  : ave=736.757 s^2=577721
new_bozo : ave=31.6 s^2=284.402

となぜボゴソートの方がループ回数が少ないのかは不明(nが小さいから?)であるが誤差の範囲内であるとするが、効率化されたボゾソートのループ回数は圧倒的に減少していることがわかる。

以上からボゴソートとボゾソートとその改良を行ってみた。まだまだアルゴリズム力と実装力が貧弱なので練習していきたいなとは思う。(テスト勉強は?)