【C#】ボゾソートを実装してみる

はじめに

前回適当に並べてソートをするボゴソートを実装しました。
www.hanachiru-blog.com

このボゴソートに並ぶ効率の悪いアルゴリズムとして知られているボゾソートを実装してみたいと思います。

仕組み

ボゾソートもすごいシンプルです。

1. ソートされているか調べ、ソートされていたら終了
2. ランダムに2つの要素を入れ替え１に戻る

これも計算量で、最弱のソートのアルゴリズムのひとつといえるでしょう。

コード

public class BozoSort<T> where T : IComparable<T>
{
    IComparer _comparer;

    public IEnumerable<T> Sort(IEnumerable<T> collection, IComparer comparer = null)
    {
        _comparer = comparer;
        var target = collection.ToArray();
        var random = new System.Random();

        while (true)
        {
            var isSorted = true;

            // ソートされているか調べる
            for(int i = 0; i < target.Length - 1; i++)
            {
                if(Compare(target[i], target[i+1]) > 0){
                    isSorted = false;
                    break;
                }
            }

            if (isSorted) break;

            // ランダムに2つの要素を入れ替える
            var x = random.Next(target.Length);
            var y = random.Next(target.Length);
            Swap(ref target[x], ref target[y]);
        }

        return target;
    }

    private int Compare(T a, T b)
    {
        if (_comparer == null) return a.CompareTo(b);
        return _comparer.Compare(a, b);
    }

    /// <summary>
    /// 参照を入れ替える(値型だと変数のコピーになってしまうため)
    /// </summary>
    private void Swap(ref T x, ref T y)
    {
        var tmp = x;
        x = y;
        y = tmp;
    }
}

使い方

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

    var bozo = new BozoSort<int>();

    foreach (var item in bozo.Sort(target))
    {
        Console.WriteLine(item);    // 1 2 3 4 5
    }
}

降順にしたい場合は比較方法を変えます。

foreach (var item in bozo.Sort(target, Comparer<int>.Create((x, y) => (int) (y - x))))
{
    Console.WriteLine(item);    // 5 4 3 2 1
}

さいごに

要素が５個ぐらいなら余裕ですぐ終わりますが、要素がもっと増えてくると地獄のような運ゲーになると思います。

怖くて私は試していませんが、もし良かったら色々な値で試してみてください。

ではまた。