Javaで学ぶアルゴリズム -シェルソート

シェルソート

挿入ソートの良さ（ソート済みに近い状態では高速）を活かし、また欠点（挿入先が離れている場合は移動回数が増える）を補うようなソートアルゴリズム。クイックソートが出てくるまでは最速だった。

シェルソート（改良挿入ソート、英語: Shellsort, Shell sort, Shell's method）は、1959年にドナルド・シェルが開発したソートのアルゴリズム。挿入ソートの一般化であり、配列の中である程度間隔が離れた要素の組ごとに挿入ソートを行い、間隔を小さくしながら同様のソートを繰り返すことで高速化するアルゴリズムである。ただし、挿入ソートと異なり、安定ソートではなくなる。

実行環境

• JUnit 5
• Java 8

テストコード

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 ShellSortTest {

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

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

		int[] actual = ShellSort.shellSort(array);
		assertThat(actual, is(expected));
	}

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

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

シェルソートアルゴリズム

public class ShellSort {

	/**
	 * シェルソート（挿入ソートの改良版）
	 * 挿入ソートのメリットを活かし、デメリットを補うアルゴリズム
	 * @param array
	 * @return sortedArray
	 */
	public static int[] shellSort(int[] array) {
		int[] sortedArray = array.clone();
		// h-ソートの間隔を決定
		// 間隔の決定方法はいくつかあり、最適は場合による
		// 以下は Knuth さんが提案した方法
		int h = 1;
		while (h < sortedArray.length / 3) {
			h = h * 3 + 1;
		}

		// 間隔を縮小していきながらソート
		while (h >= 1) {
			for (int i = h; i < sortedArray.length; i++) {
				int temp = sortedArray[i];
				int j;
				for (j = i; j >= h && sortedArray[j - h] > temp; j -= h) {
					sortedArray[j] = sortedArray[j - h];
				}
				sortedArray[j] = temp;
			}
			h = h / 3; // 間隔を縮小
		}
		return sortedArray;
	}
}