📌

Rustで最悪のソートアルゴリズム「ボゴソート」を実装してみた

2025/12/16に公開

2026/04/07

こんにちは。

今回は、ソートアルゴリズムの中でも特に非効率的として知られる「ボゴソート (Bogo Sort)」をRustで実装し、その恐ろしさを体験してみましょう。

※筆者はRust初心者です。

 ボゴソートとは？ボゴソートは、「まぬけなソート」や「モンキーソート」とも呼ばれる、実用には全く向かないソートアルゴリズムです。  その手順は非常にシンプルで、ある意味、大胆です。
ランダムに要素を並び替える（シャッフルする）。
配列がソートされているか確認する。
ソートされていなければ、1に戻る。
はい、ひたすらランダムに並び替えて、たまたまソートされるのを待つだけです。

 計算量の話（ちょっとだけ）平均計算量: O(n \cdot n!)

最悪計算量: 無限大

一般的に効率が良いとされるソートアルゴリズム（クイックソートやマージソートなど）の平均計算量がO(n \log n)であるのに対し、ボゴソートはO(n \cdot n!)という絶望的な計算量を持っています。これは要素数が増えるほど、ソートが完了するまでの時間が爆発的に増加することを意味します。最悪の場合、永遠にソートが完了しない可能性すらあります（非常に低い確率ですが）。

 Rustでの実装今回実装したRustのコードを見てみましょう。

main.rsから、核となるbogo_sort関数と、補助的な関数を解説します。
ボゴソートの本体 (bogo_sort)

ソート処理の核心部分です。
fn bogo_sort(mut v: Vec<i32>) -> Vec<i32> {
    use rand::seq::SliceRandom;
    use rand::thread_rng;
    let mut rng = thread_rng();

    let mut loop_count: i32 = 0;
    loop {
        // ソートされているか確認
        let mut current_val: i32 = v[0];
        let mut sorted:bool = true;
        for x in &v {
            if x < &current_val {
                sorted = false;
                break;
            } else {
                current_val = *x;
            }
        }

        // ソートされていない場合、配列をシャッフル
        if sorted == false {
            println!("\n{:?}\nソート失敗",v);
            // ここでランダムな並び替え（シャッフル）を実行
            v.shuffle(&mut rng);
            loop_count += 1;
        } else {
            println!("\nソート成功\n【{} 回シャッフルしました。】",&loop_count);
            break;
        }
    }
    v
}
loop: ソートが完了するまで無限ループを実行します。
ソート確認: forループを使って、配列の要素を先頭から順に走査し、前の要素より現在の要素が小さければ（つまり降順になっていれば）sorted = falseとしてソート失敗を記録し、ループを抜けます。
シャッフル: rand::seq::SliceRandomトレイトのshuffleメソッドを利用して、配列をランダムに並び替えています。
終了: sorted == trueになった時点でループを抜け、ソート完了です。シャッフル回数を表示しています。
ランダムな配列の生成  (create_rand_vec)

ボゴソートする対象の配列を生成します。
/// ランダムな配列を生成
fn create_rand_vec(len: usize, min: i32, max: i32) -> Vec<i32> {
    use rand::Rng;
    let mut rng = rand::thread_rng();
    (0..len).map(|_| rng.gen_range(min..=max)).collect()
}
randクレートのRngトレイトを使って、指定された最小値(MIN)から最大値(MAX)の間のランダムな整数を、指定された長さ(LEN)だけ生成しています。
メイン処理 (main)

配列の生成、ソートの実行、結果の表示を行っています。
const LEN: usize = 5; // 要素数
const MIN: i32 = 1;
const MAX: i32 = 10;

fn main() {
    // ランダムな配列を作成
    let v = create_rand_vec(LEN,MIN,MAX);
    println!("\nBefore: {:?}",&v);

    wait_enter("\nEnterでボゴソートを実行");

    // ソートを実行
    let sort_v:Vec<i32> = bogo_sort(v);
    println!("\nAfter: {:?}",sort_v);

    wait_enter("\nEnterで終了");
}
今回の設定では、要素数を5に抑えています。これは、ボゴソートが完了するまでの時間を許容範囲内にするためです。

⚠️ 要素数を10などに増やすと、ソートに数分、あるいはそれ以上かかる可能性があります
ユーザーがEnterを押すまで待機する関数
///ユーザーのEnter押下を待機
fn wait_enter(massage:&str) {
    use std::io::{self, Write};
    println!("{}",massage);
    let _ = io::stdout().flush();
    let mut s = String::new();
    let _ = io::stdin().read_line(&mut s);
}
実行例
Before: [7, 2, 10, 8, 4]

Enterでボゴソートを実行
(Enterキーを押下)

[8, 4, 10, 2, 7]
ソート失敗

[7, 8, 4, 10, 2]
ソート失敗

... (中略) ...

ソート成功
【198 回シャッフルしました。】

After: [2, 4, 7, 8, 10]

Enterで終了

 まとめ今回は、Rustを使って「ボゴソート」という非実用的なソートアルゴリズムを実装し、そのランダム性に頼る実装を体験しました。ボゴソートは、アルゴリズムの効率（計算量）がいかに重要かを理解するための最高の反面教師になります。皆さんも、自分のPCでボゴソートの恐ろしさを体験してみてはいかがでしょうか？

ボゴソートとは？

計算量の話（ちょっとだけ）

Rustでの実装

まとめ

Discussion