Javaで学ぶアルゴリズム -マージソート

マージソート

マージソートは、ソートのアルゴリズムで、既に整列してある複数個の列を1個の列にマージする際に、小さいものから先に新しい列に並べれば、新しい列も整列されている、というボトムアップの分割統治法による。大きい列を多数の列に分割し、そのそれぞれをマージする作業は並列化できる。

実行環境

• JUnit 5
• Java 8

テストコード

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

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

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

		int[] actual = MergeSort.mergeSortWrapper(array);
		assertThat(actual, is(expected));
	}

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

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

マージソートアルゴリズム

MergeSort.java

public class MergeSort {

	private static int[] tempArray;

	/**
	 * マージソートのラッパーメソッド
	 * @param array
	 * @return sortedArray
	 */
	public static int[] mergeSortWrapper(int[] array) {
		int[] sortedArray = array.clone();
		tempArray = new int[sortedArray.length];
		sortedArray = mergeSort(sortedArray, 0, sortedArray.length - 1);
		tempArray = null;
		return sortedArray;
	}

	/**
	 * マージソート：再帰処理を使った分割統治でソートする
	 * @param array
	 * @param left
	 * @param right
	 * @return ソート済みの array
	 */
	private static int[] mergeSort(int[] array, int left, int right) {
		if (array.length <= 1 || left >= right) {
			return array;
		}

		int middle = (left + right) / 2;
		mergeSort(array, left, middle); // 左側を再帰的にソートしきる
		mergeSort(array, middle + 1, right); // 右側を再帰的にソートしきる
        // 最初に呼ばれたとき上記２つのmergeSort()が終わった時点でソート済みの2つの配列が存在している

		// 左半分をtempArrayにコピー
		for (int i = left; i <= middle; i++) {
			tempArray[i - left] = array[i];
		}

		int leftIndex = 0; // 左サブ配列のインデックス
		int rightIndex = middle + 1; // 右サブ配列のインデックス
		int sortedIndex = left; // マージされた配列のインデックス

		// 左と右のサブ配列をマージ
		while (leftIndex < (middle - left + 1) && rightIndex <= right) {
			if (tempArray[leftIndex] <= array[rightIndex]) {
				array[sortedIndex++] = tempArray[leftIndex++];
			} else {
				array[sortedIndex++] = array[rightIndex++];
			}
		}

		// 左サブ配列が残っているならコピー
		while (leftIndex < (middle - left + 1)) {
			array[sortedIndex++] = tempArray[leftIndex++];
		}

		return array;
	}
}

やってること

再帰処理は頭がおかしくなりそうですが、 やっているのは divide and conquerです！！！！

1. [5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10] が与えられる
2. [5, 12, 7, 0, 1, 14, 6] と [9, 8, 3, 2, 11, 4, 13, 10] に分割
3. 左側の配列をソートするために分割する
4. [5, 12, 7] と [0, 1, 14, 6] に分割
5. [5, 12, 7] を [5, 12] と [7] に分割
6. [5] と [12] に分割
7. [0, 1, 14, 6] を [0, 1] と [14, 6] に分割
8. [0] と [1] に分割
9. [14] と [6] に分割
10. 分割した左側の配列を統合とソート
11. [5, 12] に統合
12. [5, 7, 12] に統合
13. [0, 1] に統合
14. [6, 14] に統合
15. [0, 1, 6, 14] に統合
16. [0, 1, 5, 6, 7, 12, 14] に統合
17. 次に右側の配列をソートするするために分割する
18. [9, 8, 3, 2] と [11, 4, 13, 10] に分割
19. （めんどくさいので省略）
20. 2つの配列が出来上がる
21. [0, 1, 5, 6, 7, 12, 14] と [2, 3, 4, 8, 9, 10, 11, 13, 10]
22. 2つのソート済み配列を完全に統合する
23. [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]