【C#】猿でもできるボゴソートを実装してみる

はじめに

今回は「猿でもできるソート(monkey sort)」という異名を持つボゴソートを実装してみたいと思います。

ja.wikipedia.org

はじめに
仕組み
コード
使い方
さいごに

仕組み

仕組みはめちゃくちゃにシンプルです。

要素をバラバラに並べる
ソート済みか調べ、ソートされていなければ１に戻る

簡単に言えば、適当にシャッフルされていればいずれはソートされているだろうという手法です。

計算量はなんと $O(∞)$ というソートのアルゴリズムで最弱になっています。

ただ私的にはロマンがあって嫌いじゃないですね。

コード

public static IEnumerable<T> BogoSort<T>(IEnumerable<T> collection) where T : IComparable<T>
{
    if (collection.Count() == 0) return null;

    // ループ内で何度も遅延評価を行うと速度が遅くなる場合がある気がしたので予め配列を作成
    var items = collection.ToArray();
    T[] target = null;
    var isSorted = false;

    while (!isSorted)
    {
        // ランダムに配置
        target = items.OrderBy(t => Guid.NewGuid()).ToArray();
        isSorted = true;

        for (int i = 0; i < target.Length - 1; i++)
        {
            // 昇順になっているか確認
            if (target[i].CompareTo(target[i + 1]) > 0)
            {
                isSorted = false;
                break;
            }
        }
    }

    return target;
}

使い方

static void Main(string[] args)
{
    var target = new int[] { 1, 3, 2, 5, 4 };

    foreach (var item in BogoSort<int>(target))
    {
        Console.WriteLine(item);        // 1 2 3 4 5
    }
}