Javaで学ぶアルゴリズム -クイックソート

クイックソート

クイックソート（英: quicksort）は、1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
他のソート法と比べて一般的に最も高速だと言われているが、対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量は $O(n^{2})$である。安定ソートではない。

実行環境

• JUnit 5
• Java 8

テストコード

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

	@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 = QuickSort.quickSort(array, 0, array.length - 1);
		assertThat(actual, is(expected));
	}

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

		int[] actual = QuickSort.quickSort(array, 0, array.length - 1);
		assertThat(actual, is(expected));
	}

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

		int[] actual = QuickSort.quickSort(array, 0, array.length);
		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 = QuickSort.quickSort(array, 0, array.length - 1);
		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 = QuickSort.quickSort(array, 0, array.length - 1);
		assertThat(actual, is(expected));
	}
}

クイックソートアルゴリズム

QuickSort.java

public class QuickSort {

	/**
	 * クイックソート
	 * 再帰呼び出しを使用して実装されることが一般的らしい
	 * @param array
	 * @param lower
	 * @param upper
	 * @return ソート済みの array
	 */
	public static int[] quickSort(int[] array, int lower, int upper) {

		if (array.length == 0) {
			return array;
		}
		int left = lower;
		int right = upper;
		int mid = array[(left + right) / 2];

		while (left <= right) {
			while (array[left] < mid) {
				left++;
			}
			while (array[right] > mid) {
				right--;
			}
			if (left <= right) {
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
				left++;
				right--;
			}
		}
		if (lower < right) {
			quickSort(array, lower, right);
		}
		if (upper > left) {
			quickSort(array, left, upper);
		}
		return array;
	}
}

メソッドで何してるか確認するためのデバッグ用コード

要素を入れ替える前後に配列の状態を出力するデバッグ用のコードを差し込んで確認してみる。

QuickSortTest.java

public class QuickSortTest {

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

QuickSort.java

import java.util.Arrays;

public class QuickSort {

	private static int count = 0;

	/**
	 * デバッグ用にquickSort()をラップしたメソッド
	 * @param array
	 * @return sortedArray
	 */
	public static int[] quickSortForDebug(int[] array) {
		int[] sortedArray = array.clone();
		sortedArray = quickSort(sortedArray, 0, sortedArray.length - 1);
		System.out.println(Arrays.toString(sortedArray));
		return sortedArray;
	}

	/**
	 * クイックソート
	 * 再帰呼び出しを使用して実装されることが一般的らしい
	 * @param array
	 * @param lower
	 * @param upper
	 * @return ソート済みの array
	 */
	public static int[] quickSort(int[] array, int lower, int upper) {

		if (array.length == 0) {
			return array;
		}
		int left = lower;
		int right = upper;
		int mid = array[(left + right) / 2];

		// デバッグ用
		count++;
		printForDebug(count, "Before", array, lower, upper);

		while (left <= right) {
			while (array[left] < mid) {
				left++;
			}
			while (array[right] > mid) {
				right--;
			}
			if (left <= right) {
				int temp = array[left];
				array[left] = array[right];
				array[right] = temp;
				left++;
				right--;
			}
		}
		// デバッグ用
		printForDebug(count, "After ", array, lower, upper);
		if (lower < right) {
			quickSort(array, lower, right);
		}
		if (upper > left) {
			quickSort(array, left, upper);
		}
		return array;
	}

	/**
	 * デバッグ用に配列の状態を吐き出す
	 * @param count
	 * @param label
	 * @param array
	 * @param lower
	 * @param upper
	 */
	private static void printForDebug(int count, String label, int[] array, int lower, int upper) {
		System.out.printf("[%d周目 %s] array[%d] ~ [%d]:{", count, label, lower, upper);
		for (int i = lower; i <= upper; i++) {
			System.out.printf("%d", array[i]);
			if (i < upper) {
				System.out.print(" , ");
			}
		}
		System.out.println("}");
	}
}

※ 分かりやすくするために改行入れてます

デバッグ出力の内容

[1周目 Before] array[0] ~ [14]:{5 , 12 , 7 , 0 , 1 , 14 , 6 , 9 , 8 , 3 , 2 , 11 , 4 , 13 , 10}
[1周目 After ] array[0] ~ [14]:{5 , 4 , 7 , 0 , 1 , 2 , 6 , 3 , 8 , 9 , 14 , 11 , 12 , 13 , 10}

[2周目 Before] array[0] ~ [8]:{5 , 4 , 7 , 0 , 1 , 2 , 6 , 3 , 8}
[2周目 After ] array[0] ~ [8]:{1 , 0 , 7 , 4 , 5 , 2 , 6 , 3 , 8}

[3周目 Before] array[0] ~ [1]:{1 , 0}
[3周目 After ] array[0] ~ [1]:{0 , 1}

[4周目 Before] array[2] ~ [8]:{7 , 4 , 5 , 2 , 6 , 3 , 8}
[4周目 After ] array[2] ~ [8]:{2 , 4 , 5 , 7 , 6 , 3 , 8}

[5周目 Before] array[3] ~ [8]:{4 , 5 , 7 , 6 , 3 , 8}
[5周目 After ] array[3] ~ [8]:{4 , 5 , 3 , 6 , 7 , 8}

[6周目 Before] array[3] ~ [6]:{4 , 5 , 3 , 6}
[6周目 After ] array[3] ~ [6]:{4 , 3 , 5 , 6}

[7周目 Before] array[3] ~ [4]:{4 , 3}
[7周目 After ] array[3] ~ [4]:{3 , 4}

[8周目 Before] array[5] ~ [6]:{5 , 6}
[8周目 After ] array[5] ~ [6]:{5 , 6}

[9周目 Before] array[7] ~ [8]:{7 , 8}
[9周目 After ] array[7] ~ [8]:{7 , 8}

[10周目 Before] array[9] ~ [14]:{9 , 14 , 11 , 12 , 13 , 10}
[10周目 After ] array[9] ~ [14]:{9 , 10 , 11 , 12 , 13 , 14}

[11周目 Before] array[9] ~ [10]:{9 , 10}
[11周目 After ] array[9] ~ [10]:{9 , 10}

[12周目 Before] array[12] ~ [14]:{12 , 13 , 14}
[12周目 After ] array[12] ~ [14]:{12 , 13 , 14}

ソート結果
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]