Javaで学ぶアルゴリズム -度数ソート

度数ソート

度数ソートはソートアルゴリズムの一種。ヒストグラムソートとも。
バケットソート系のアルゴリズムであり、試験の点数の集計など上限下限が定まった統計値の処理で威力を発揮する。

比較の必要がないアルゴリズム。

実行環境

• JUnit 5
• Java 8

テストコード

CountSortTest.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 CountSortTest {

	@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 = CountSort.countSort(array);
		assertThat(actual, is(expected));
	}

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

		int[] actual = CountSort.countSort(array);
		assertThat(actual, is(expected));
	}

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

		int[] actual = CountSort.countSort(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 = CountSort.countSort(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 = CountSort.countSort(array);
		assertThat(actual, is(expected));
	}
}

度数ソートアルゴリズム

CountSort.java

public class CountSort {

	/**
	 * 度数ソート / カウントソート（渡される配列の要素が0以上であることを前提とする）
	 * @param array
	 * @return sortedArray
	 */
	public static int[] countSort(int[] array) {
		if (array.length == 0) {
			return array;
		}

		int maxVal = findMaxValue(array);
		// 各値の出現回数をカウントし、その後に累積和を計算するために使用
		int[] countArray = new int[maxVal + 1];
		int[] sortedArray = new int[array.length];

		// 各値の出現回数をカウント（度数分布表の作成）
		for (int i = 0; i < array.length; i++) {
			countArray[array[i]]++;
		}

		// デバッグ
		System.out.println("DEBUG：出現回数を出力");
		printArray(countArray);

		// 累積和を計算（累積度数分布表の作成）
		for (int i = 1; i < countArray.length; i++) {
			countArray[i] += countArray[i - 1];
		}

		// デバッグ
		System.out.println("DEBUG：累積和を出力");
		printArray(countArray);

		// 返す配列にソートされた値を配置
		for (int i = array.length - 1; i >= 0; i--) {
			// 現在の値の正しい位置を決定（累積配列を基に計算）
			sortedArray[countArray[array[i]] - 1] = array[i];
			// その値の出現回数をデクリメント
			countArray[array[i]]--;
		}

		return sortedArray;
	}

	/**
	 * 配列の最大値を探す
	 * @param array
	 * @return maxVal
	 */
	private static int findMaxValue(int[] array) {
		int maxVal = array[0];
		for (int value : array) {
			if (value > maxVal) {
				maxVal = value;
			}
		}
		return maxVal;
	}

	// デバッグ用メソッド
	private static void printArray(int[] array) {
		for (int value : array) {
			System.out.print(value + " ");
		}
		System.out.println();
	}
}

デバッグ出力

テスト１

	@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 = CountSort.countSort(array);
		assertThat(actual, is(expected));
	}

DEBUG：出現回数を出力
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 
DEBUG：累積和を出力
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 

テスト２

	@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 = CountSort.countSort(array);
		assertThat(actual, is(expected));
	}

DEBUG：出現回数を出力
0 1 2 3 0 5 
DEBUG：累積和を出力
0 1 3 6 6 11