ActionScript入門Wiki - バケットソート

トップページ > アルゴリズム > バケットソート

アルゴリズム

まずは、ソート対象の配列を用意します。
例:[2, 3, 5, 2, 5, 2]

要素の値の数をカウントします。
上の配列だと、

2が3個
3が1個
5が2個

になりますね。

それを値の小さい順に取り出して並べます。

2が3個 → 2, 2, 2
3が1個 → 2, 2, 2, 3
5が2個 → 2, 2, 2, 3, 5, 5

並べた2, 2, 2, 3, 5, 5がソートした結果になります。

値の数をカウントするには配列を使用しましょう。

[2, 3, 5, 2, 5, 2]の各要素を、自分の値と同じインデックスの所に放り込むだけです。
実際は配列の各要素を0で初期化しておき、放り込むときに値をインクリメントします(例:値が3だったら、配列[3]++と記述する)
これでカウントは出来たので、後は[0]～[5]までを走査し、値が0以外のところだけを取り出します。

[0]の中身は0 → []
[1]の中身は0 → []
[2]の中身は3 → [2, 2, 2]
[3]の中身は1 → [2, 2, 2, 3]
[4]の中身は0 → [2, 2, 2, 3]
[5]の中身は2 → [2, 2, 2, 3, 5, 5]

になります。

欠点

1

まず、ソート対象の値の最大値が分かっていないと使用できません。
でないと、値をカウントする際に使用する配列が初期化出来ないからです。(配列のサイズが決められない)
undefinedだったら1にする、という方法もありますが、それは他の言語でも使えるとは限りません。(汎用的ではない)

2

上の例のように各要素の数値が小さければ問題は無いのですが、例えば4000万という数値が入っていれば、配列のサイズも4000万にしないといけないという問題があります。
つまり、あまり大きい値をこのアルゴリズムでソートすることは出来ません。

3

配列のインデックスと対応させるため、整数以外の値をソートすることが出来ません。

プログラム

private function bucketSort(data:Array, max:int):void
{
	// 各要素の値をカウントするための配列を用意。
	// サイズはmaxで、各要素を0で初期化する
	var bucket:Array = new Array(max);
	for (var i:int = 0; i < bucket.length; i++)
	{
		bucket[i] = 0;
	}
 
	// 各要素の値に対応するインデックスの中身をインクリメントする
	// (例:値がmなら、bucket[m]++)
	for (i = 0; i < data.length; i++)
	{
		bucket[data[i]]++;
	}
 
	// バケットの中身を[0]～[max - 1]まで走査
	for (var j:int = i = 0; i < bucket.length; i++)
	{
		// 取り出した中身が0でない限りループ
		// 0以外だったら値を取り出して、その後デクリメントする(減らす)
		for (var k:int = bucket[i]; k > 0; k--)
		{
			data[j++] = i;
		}
	}
}

バケットソートを行うメソッドです。

var data:Array = [2, 3, 0, 1, 8, 9, 5, 6, 7, 4];
bucketSort(data, 10);
trace(data); // 0,1,2,3,4,5,6,7,8,9

実行結果です。

検証用コード

package
{
	import flash.display.Sprite;
 
	public class Main extends Sprite
	{
		public function Main()
		{
			var data:Array = [2, 3, 0, 1, 8, 9, 5, 6, 7, 4];
			bucketSort(data, 10);
			trace(data); // 0,1,2,3,4,5,6,7,8,9
		}
 
		private function bucketSort(data:Array, max:int):void
		{
			var bucket:Array = new Array(max);
			for (var i:int = 0; i < bucket.length; i++)
			{
				bucket[i] = 0;
			}
 
			for (i = 0; i < data.length; i++)
			{
				bucket[data[i]]++;
			}
 
			for (var j:int = i = 0; i < bucket.length; i++)
			{
				for (var k:int = bucket[i]; k > 0; k--)
				{
					data[j++] = i;
				}
			}
		}
	}
}

リンク元(0)

添付ファイル

s1.png