Javaで学ぶアルゴリズム -挿入ソート

挿入ソート

挿入ソート（そうにゅうソート、英: insertion sort）あるいは基本挿入法は、ソートのアルゴリズムの一つ。整列してある配列に追加要素を適切な場所に挿入すること。

実行環境

• JUnit 5
• Java 8

テストコード

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

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

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

		int[] actual = InsertionSort.insertionSort(array);
		assertThat(actual, is(expected));
	}

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

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

挿入ソートアルゴリズム

InsertionSort.java

public class InsertionSort {

	/**
	 * 挿入ソート（シャトルソートとも呼ばれる）
	 * keyを保持しておいて、それより大きい要素を1つずつ後ろにずらしていく
	 * @param array
	 * @return sortedArray
	 */
	public static int[] insertionSort(int[] array) {
		int[] sortedArray = array.clone();
		for (int i = 1; i < sortedArray.length; i++) {
			int key = sortedArray[i];
			int j = i - 1;

			// keyより大きい要素を一つ後ろに移動
			while (j >= 0 && sortedArray[j] > key) {
				sortedArray[j + 1] = sortedArray[j];
				j = j - 1;
			}
			// keyを適切な位置に挿入
			sortedArray[j + 1] = key;
		}
		return sortedArray;
	}
}

おまけ：２分挿入ソートアルゴリズム

BinaryInsertionSort.java

public class BinaryInsertionSort {

	/**
	 * ２分探索と組み合わせた挿入ソート
	 * 単純挿入ソートは安定だけどこっちは安定ではなくなる
	 * @param array
	 * @return sortedArray
	 */
	public static int[] binaryInsertionSort(int[] array) {
		int[] sortedArray = array.clone();
		for (int i = 1; i < sortedArray.length; i++) {
			int key = sortedArray[i];
			int insertionIndex = binarySearch(sortedArray, key, i);

			for (int j = i; j > insertionIndex; j--) {
				sortedArray[j] = sortedArray[j - 1];
			}
			sortedArray[insertionIndex] = key;
		}
		return sortedArray;
	}

	/**
	 * 二分探索
	 * @param array
	 * @param target
	 * @param end
	 * @return start
	 */
	public static int binarySearch(int[] array, int target, int end) {

		int start = 0;

		while (start < end) {
			int mid = (start + end) / 2; // 中央のインデックスを計算
			if (array[mid] < target) {
				start = mid + 1; // 探索範囲を後半に絞り込む
			} else {
				end = mid; // 探索範囲を前半に絞り込む
			}
		}
		return start;
	}
}