【C++】BogoSort（ボゴソート／順列ソート）の実装プログラム

ボゴソート（Bogosort）は、配列が整列するまで要素をランダムにシャッフルし続けるという、非常にシンプルな仕組みのソートアルゴリズムです。順列と組み合わせの考え方に基づいた非効率な手法であることから、「順列ソート（Permutation Sort）」とも呼ばれています。

また、その非効率さから「ショットガンソート」「バカソート（Stupid Sort）」「モンキーソート」「スローソート」といった別名でも知られています。このアルゴリズムは、入力データの順列を次々と生成し、たまたま整列された並びが出現するまで処理を繰り返します。

入力：53421
出力：12345

アルゴリズムの仕組み

ボゴソートの動作手順は以下の通りです。

1. 配列の要素が昇順に整列されているかどうかをチェックします。
2. 整列されていない場合は、配列内の要素をランダムに入れ替え（シャッフル）ます。
3. 整列が確認できるまで、チェックとシャッフルを繰り返します。

つまり、正しい並びが偶然完成するまで延々とシャッフルを続けるため、最悪計算量は無限大になり得るという、理論上ほとんど実用性のないアルゴリズムです。ただし、その単純さゆえに学習用の題材としてよく取り上げられます。

C++による実装例

#include <iostream>
#include <stdlib.h>
using namespace std;

// 配列がソート済みかどうかを判定する関数
int is_sorted(int *arr, int n) {
    while ( --n >= 1 ) {
        if ( arr[n] < arr[n-1] ) {
            return 0;
        }
    }
    return 1;
}

// 配列をランダムにシャッフルする関数
void shuffle(int *arr, int n) {
    int temp, r;
    for(int i=0; i < n; i++) {
        temp = arr[i];
        r = rand() % n;
        arr[i] = arr[r];
        arr[r] = temp;
    }
}

// ソート完了までシャッフルを繰り返す関数
void bogosort(int *arr, int n) {
    while ( !is_sorted(arr, n) ) {
        shuffle(arr, n);
    }
}

int main() {
    int arr[] = { 5, 3, 4, 2, 1 };
    int i;
    bogosort(arr, 5);
    for (i=0; i < 5; i++) {
        cout<< arr[i]<<"\t";
    }
}

コードの解説

• is_sorted関数： 配列の隣接する要素同士を比較し、一箇所でも逆順になっている場合は 0 を返します。すべて整列していれば 1 を返します。
• shuffle関数： rand() 関数を使ってランダムなインデックスを選び、要素を入れ替えることで配列全体をシャッフルします。
• bogosort関数： is_sorted が 1（ソート済み）を返すまで、shuffle を繰り返し呼び出します。

このプログラムを実行すると、{ 5, 3, 4, 2, 1 } の配列が最終的に 1 2 3 4 5 と昇順に出力されます。ただし、要素数が増えるほど整列するまでの試行回数は爆発的に増加するため、あくまで学習・実験目的のサンプルである点に注意してください。