はじめに
前回はバケットソートを紹介しましたが、今回はその改良版とも言われる基数ソートについて実装していきたいと思います。
ja.wikipedia.org
バケットソートではバケットの数が膨大になってしまうのはNGという制約がありました。計算量と引き換えにそのバケット数を少なくしようというのがこのアルゴリズムの目的になります。
早速みていきましょう。
基数ソート
アルゴリズム自体の発想はシンプルで、各桁に対してバケットソートを行います。
実際に例をみてみて方が分かりやすいでしょう。
0回目: 100, 2, 15, 153, 205, 26
1回目(1桁目): 100, 2, 153, 15, 205, 26
2回目(2桁目): 100, 2, 205, 153, 15, 26
3回目(3桁目): 2, 15, 26, 100, 153, 205
このように各桁に適応することでバケットの数は10個だけで済ませることができました。
ちなみに元の配列の前後関係が反服後も保存されているという安定ソートという性質をバケットソートがもっているからできる芸当になります。
また10進数だとこのようになりますが、256進数にしてみたりと色々な高速化がなされる場合もあるようです。
実装
/// <summary> /// 基数ソート /// </summary> public static int[] RadixSort(IEnumerable<int> items) { var nums = items.ToArray(); var n = nums.Length; // log10を使って桁数を求める var max = nums.Max(); var k = (max == 0) ? 1 : ((int)Math.Log10(max) + 1); // 10進数の時の各桁をみるため,バケットは10個で固定 var bucket = new List<int>[10]; // 各桁に対してバケットソート for (int d = 0; d < k; d++) { // バケットにすべてのデータを入れる for (int i = 0; i < n; i++) { // d桁目の値 var target = (nums[i] / (int)Math.Pow(10, d)) % 10; if (bucket[target] == null) bucket[target] = new List<int>(); bucket[target].Add(nums[i]); } // バケツの順番に取り出し,配列に格納 var index = 0; for (int i = 0; i < bucket.Length; i++) { if (bucket[i] == null) continue; foreach (var item in bucket[i]) { nums[i] = item; index++; } } // バケットを空にする bucket = bucket.Select(t => t = null).ToArray(); } return nums; }
テスト
使い方はこんな感じ。
static void Main(string[] args) { var a = new int[] { 170, 45, 75, 90, 2, 24, 802, 66 }; foreach (var item in BucketSort(a)) Console.WriteLine(item); // 2, 24, 45, 66, 75, 90, 170, 802 }
考察
アルゴリズムの性能をみるために計算量をみてみましょう。
基数ソートはバケットソートを桁数k回だけ繰り返します。
バケットソートの最悪計算量はo(m + n)
(nは要素数,mはバケットの数)を考慮すると,最悪計算量はo(km + kn)
だと導けます。
さいごに
基数ソートはバケットソートを各桁に対して行うというアルゴリズムでしたが、発想としては結構面白いですよね。
次はヒープソートを扱ってみようかなとも思ってます。
よかったらそちらもみてみてください。
ではまた。