バケツソート

バケツソートとは？

世の中には様々なソート方法があります。
例として、

• 選択ソート
• バブルソート
• 挿入ソート
• シェルソート
• マージソート
• クイックソート
• ヒープソート

などがあります。
処理の複雑さ、計算量等それぞれのソート方法に長所、短所があり、状況によって使い分ける必要があるそうです。

ここで、「0～99の範囲の整数が格納された要素数100の配列をソートする」場合を考えてみます。
この場合に有効といわれているのが「バケツソート」と呼ばれるソート方法です。

その方法は、

1.データの値を要素番号とした受け皿（以後バケツ）を100個用意する
2.バケツのなかに該当要素番号が出現した回数を入れる

です。
バケツの要素番号を中身の回数分繰り返し表示したら、ソート後の内容を確認することができます。

具体例

スケールの小さな具体例を示したいと思います。
「0～5の範囲の整数が格納された要素数6の配列をソートする」
ことを考えるとして、ソート前の元データを
{３，４，１，１，１，３}
とします。
この時、１番目のバケツには、０のデータは一つもないので、０が入ります。
１番目のバケツには、１が３つあるので、３が入ります。
この操作を繰り返していくと、バケツ配列の中身は、
{０，３，０，２，１，０}
となります。

Java実装

このバケツソートをJavaで実装したものが以下になります。

public class BucketSort {
	// データの数
	private static final int DATA_NUM = 100;

	public static void main(String[] args) {
		int[] data = new int[DATA_NUM];
		int[] bucket = new int[DATA_NUM];
		// データにランダムな数入れる（０～１００）
		for (int i = 0; i < DATA_NUM; i++) {
			data[i] = (int) Math.floor(Math.random() * 100);
		}
		showData(data);
		sort(data, bucket, DATA_NUM);
		// 見やすいよう改行
		System.out.println();
		showBucket(bucket, DATA_NUM);
	}

	// 元のデータ表示
	private static void showData(int[] data) {
		for (int ele : data) {
			System.out.print("[" + ele + "]");
		}
	}

	// ソート後のバケツの中身表示
	private static void showBucket(int[] bucket, int length) {
		for (int i = 0; i < length; i++) {
			if (bucket[i] > 0) {
				for (int j = 0; j < bucket[i]; j++) {
					System.out.print("[" + i + "]");
				}
			}
		}
	}

	// バケツソートロジック
	private static void sort(int[] data, int[] bucket, int length) {
		for (int i = 0; i < length; i++) {
			bucket[data[i]]++;
		}
	}
}

texthttps://github.com/nannany/bucket-sort/blob/master/src/main/java/bucketsort/BucketSort.java

以上です。