Javaで学ぶアルゴリズム -バケットソート

バケットソート

バケットソート(ビンソート [Bin Sort] とも呼ばれる)はあらかじめデータがとりうる値すべての容器(バケット)を順番どおりに並べて用意しておき、値を対応する容器に移すことでソートを行う整列アルゴリズムです。

データがとりうる値がわかっていなければソートのためのバケット [Bucket] を準備することができないのでこのアルゴリズムは使えません。比較を用いない整列アルゴリズムです。

実行環境

• JUnit 5
• Java 8

テストコード

BucketSortTest.java

import static org.hamcrest.CoreMatchers.is;
import static org.hamcrest.MatcherAssert.assertThat;

import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.api.Test;

public class BucketSortTest {

	@DisplayName("配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchange() {
		int[] array = { 5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("要素が1つしかない配列を渡すと要素が1つしかない配列が返ること")
	@Test
	void testStraightExchangeOneElement() {
		int[] array = { 5 };
		int[] expected = { 5 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("空の配列を渡すと空の配列が返ること")
	@Test
	void testStraightExchangeEmpty() {
		int[] array = {};
		int[] expected = {};

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("すでに昇順でソートされた配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchangeAlreadySorted() {
		int[] array = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

	@DisplayName("要素が重複した配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchangeDuplicateElement() {
		int[] array = { 5, 3, 5, 2, 1, 5, 3, 2, 5, 3, 5 };
		int[] expected = { 1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}
}

バケットソートアルゴリズム

BucketSort.java

import java.util.Arrays;

public class BucketSort {

	/**
	 * バケットソートだが、実装自体は度数ソートに近い
	 * @param array
	 * @return sortedArray
	 */
	public static int[] bucketSort(int[] array) {
		int[] sortedArray = array.clone();
		if (sortedArray.length == 0) {
			return sortedArray;
		}

		// 配列の最大値と最小値を見つける
		int maxValue = sortedArray[0];
		int minValue = sortedArray[0];
		for (int num : sortedArray) {
			if (num > maxValue) {
				maxValue = num;
			}
			if (num < minValue) {
				minValue = num;
			}
		}

		// バケットの数を決定
		int[][] buckets = new int[maxValue - minValue + 1][0];

		// 各要素を対応するバケットに追加
		for (int num : sortedArray) {
			int bucketIndex = num - minValue;
			buckets[bucketIndex] = appendToArray(buckets[bucketIndex], num);
		}

		// デバッグ用
        printForDebug(buckets);

		// 各バケットを順に結合
		int index = 0;
		for (int[] bucket : buckets) {
			Arrays.sort(bucket); // 各バケット内をソート
			for (int num : bucket) {
				sortedArray[index++] = num; // ソートされているバケットを元の配列に追加
			}
		}
		return sortedArray;
	}

	/**
	 * 配列に要素を追加する
	 * @param array
	 * @param value
	 * @return array
	 */
	private static int[] appendToArray(int[] array, int value) {
		array = Arrays.copyOf(array, array.length + 1);
		array[array.length - 1] = value;
		return array;
	}

	/**
	 * デバッグ用: バケットに格納された後の状況を出力
	 * @param buckets
	 */
	private static void printForDebug(int[][] buckets) {
		System.out.println("Buckets after element insertion:");
		for (int i = 0; i < buckets.length; i++) {
			System.out.println("Bucket " + i + ": " + Arrays.toString(buckets[i]));
		}
	}
}

デバッグ出力

テスト１

	@DisplayName("配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchange() {
		int[] array = { 5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

出力結果

Buckets after element insertion:
Bucket 0: [0]
Bucket 1: [1]
Bucket 2: [2]
Bucket 3: [3]
Bucket 4: [4]
Bucket 5: [5]
Bucket 6: [6]
Bucket 7: [7]
Bucket 8: [8]
Bucket 9: [9]
Bucket 10: [10]
Bucket 11: [11]
Bucket 12: [12]
Bucket 13: [13]
Bucket 14: [14]

テスト２

	@DisplayName("要素が重複した配列を渡すとソートされた配列が返ること")
	@Test
	void testStraightExchangeDuplicateElement() {
		int[] array = { 5, 3, 5, 2, 1, 5, 3, 2, 5, 3, 5 };
		int[] expected = { 1, 2, 2, 3, 3, 3, 5, 5, 5, 5, 5 };

		int[] actual = BucketSort.bucketSort(array);
		assertThat(actual, is(expected));
	}

出力結果

Buckets after element insertion:
Bucket 0: [1]
Bucket 1: [2, 2]
Bucket 2: [3, 3, 3]
Bucket 3: []
Bucket 4: [5, 5, 5, 5, 5]