C++で学ぶボゴソート（順列ソート）の仕組みと実装方法

本記事では、「ボゴソート（Bogo Sort）」と呼ばれるユニークなソートアルゴリズムについて解説します。ボゴソートは「順列ソート（Permutation Sort）」「バカソート（Stupid Sort）」「スローソート（Slow Sort）」など、さまざまな名前でも知られています。

ボゴソートは、実用性という点では極めて非効率なソート手法です。このアルゴリズムは「生成と検証（Generate and Test）」パラダイムに分類され、リストがソートされるまで要素の並び替え（シャッフル）を繰り返し生成し続けます。発想自体は非常にシンプルで、「リストがソート済みになるまで、ひたすら要素をシャッフルする」というものです。

アルゴリズムの手順

bogoSort(array, n)

Begin
    while 配列 arr がソートされていない間、繰り返す
        arr をシャッフルする
    done
End

このように、ボゴソートのロジックは数行で表現できるほど単純ですが、その動作は運任せに近いため、最悪の場合には完了まで膨大な時間を要する可能性があります。

C++による実装例

以下は、ボゴソートをC++で実装したサンプルコードです。補助関数として、配列がソート済みかどうかを判定する isSorted() と、配列をランダムに入れ替える shuffle() を使用しています。

#include<iostream>
#include<cstdlib>
using namespace std;

// リストがソート済みかどうかを判定する関数
bool isSorted(int arr[], int n) {
    while (--n > 1)
        if (arr[n] < arr[n - 1])
            return false;
    return true;
}

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

// ボゴソート本体：ソートされるまでシャッフルを繰り返す
void bogoSort(int arr[], int n){
    while (!isSorted(arr, n))
        shuffle(arr, n);
}

main() {
    int data[] = {54, 74, 98, 5, 98, 32, 20, 13, 35, 40};
    int n = sizeof(data)/sizeof(data[0]);
    cout << "Sorted Sequence ";
    bogoSort(data, n);
    for(int i = 0; i <n;i++){
        cout << data[i] << " ";
    }
}

実行結果

Sorted Sequence 5 13 20 32 35 40 54 74 98 98

このコードを実行すると、シャッフルを繰り返すうちに偶然ソート済みの状態になり、上記のように昇順に並んだ結果が出力されます。

計算量について

ボゴソートの平均計算量は O((n+1)!) であり、最悪ケースでは終了時間が保証されません。10個程度の要素でもソート完了までに長い時間がかかることがあるため、あくまで学習や娯楽目的のアルゴリズムとして理解しておくとよいでしょう。実務ではクイックソートやマージソートなど、効率的なソートアルゴリズムを使用することが推奨されます。