PythonでBogoSort（順列ソート）を実装する方法を解説

この記事では、BogoSort（ボゴソート）とも呼ばれる「順列ソート」をPythonで実装する方法について解説します。

問題の概要

問題文： 与えられた配列を、順列ソートの考え方を使って並べ替えます。

BogoSortは「生成と検証（generate and test）」というパラダイムに基づいたソートアルゴリズムです。仕組みは非常にシンプルで、以下の手順を繰り返します。

• 配列がソート済みかどうかを確認する
• ソート済みでなければ、配列をランダムにシャッフルする
• ソート済みになるまでこの処理を繰り返す

最悪の場合、計算量は O((n+1)!) となり、実用性はほとんどありませんが、アルゴリズムの学習や乱数の挙動を理解するうえで興味深い例題です。

実装例

# randomモジュールをインポート
import random

# ソート本体
def bogoSort(a):
    n = len(a)
    while (is_sorted(a) == False):
        shuffle(a)

# ソート済みかどうかのチェック
def is_sorted(a):
    n = len(a)
    for i in range(0, n-1):
        if (a[i] > a[i+1]):
            return False
    return True

# ランダムな順列へのシャッフル
def shuffle(a):
    n = len(a)
    for i in range(0, n):
        r = random.randint(0, n-1)
        a[i], a[r] = a[r], a[i]

# メイン処理
a = [1, 5, 3, 4, 8, 6, 3, 4, 5]
bogoSort(a)
print("Sorted array :")
for i in range(len(a)):
    print(a[i], end=" ")

出力結果

Sorted array is :
1 3 3 4 4 5 5 6 8

コードのポイント

• bogoSort関数： 配列がソートされるまでshuffleを繰り返し呼び出すメインループです。
• is_sorted関数： 隣接する要素を先頭から順に比較し、降順のペアがひとつでもあればFalseを返します。すべて昇順ならTrueを返します。
• shuffle関数： random.randint()でランダムなインデックスを選び、要素を入れ替えることで配列全体をシャッフルします。

すべての変数はローカルスコープ内で宣言されており、各関数が独立した役割を持つシンプルな構成になっています。

まとめ

この記事では、Pythonを使ってBogoSort（順列ソート）を実装する方法を紹介しました。実行速度の面では非効率ですが、「生成と検証」という基本的なアルゴリズム設計の考え方を学ぶのに適した題材です。ぜひ実際にコードを動かして、その動作を体感してみてください。