【C#】バケットソートを実装してみる

はじめに

前回は挿入ソートを紹介しましたが、今回はバケットソートを実装していきたいと思います。

バケットソートはソートアルゴリズムでよくある要素を交換する手法を取らない面白いアルゴリズムです。
ja.wikipedia.org

また以下の制約を満たさなければ動作しませんが、条件をみたしさえすればかなり優秀に動作するアルゴリズムでもあります。

• 配列の要素のとりうる範囲が大きくなりすぎない(バケットの数が非常に多くならない)

早速みていきましょう。

バケットソート

仕組みは以下の動画が分かりやすかったので、そちらをみていただければと思います。
www.youtube.com

実装

この実装では0以上の整数しか扱いえませんが，少し工夫をすれば負の値もできるようになります。

/// <summary>
/// バケットソート
/// </summary>
public static int[] BucketSort(IEnumerable<int> items)
{
    var nums = items.ToArray();
    var max = nums.Max();

    // バケツを用意
    var bucket = new int[max + 1];

    // バケツに全てののデータを入れる(出現回数をカウントする)
    foreach (var item in nums) bucket[item]++;

    // バケツの順番に取り出し，配列に格納
    var index = 0;
    for (int i = 0; i < bucket.Length; i++)
    {
        for (int j = 0; j < bucket[i]; j++)
        {
            nums[index] = i;
            index++;
        }
    }

    return nums;
}

テスト

使い方はこんな感じ。

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

    foreach (var item in BucketSort(a))
        Console.WriteLine(item);    // 1, 2, 3, 4, 5, 6, 7
}

考察

アルゴリズムの性能を評価するために計算量を考えてみましょう。

まずm個のバケットを用意する(今回は要素の最大値がm)ためにo(m)かかります。

次にバケットを入れるのにo(n)，配列に戻すのにo(n + m)となります。

よって全体の最悪計算量はo(n + m)(配列の要素数+バケットの数)となります。

さいごに

一見難しそうなアルゴリズムに見えますが、蓋を開けてみると非常にシンプルなアルゴリズムでした。

それに加えて条件さえみたしていれば処理速度も早いので結構良い感じでしたね。

今回はこれくらいで。

ではまた。