Javaで学ぶアルゴリズム -最適化バブルソート

最適化（打ち切りありの）バブルソート

• 隣り合う要素の大小を比較しながら整列させるバブルソートに、「打ち切り」の処理を加えたもの
• 完全ランダムな配列にはほぼ効果がないが、一部ソートされているものには効果を発揮する

実行環境

• 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 OptimizedBubbleSortTest {

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

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

		int[] actual = OptimizedBubbleSort.bubbleSortWithEarlyStop(array);
		assertThat(actual, is(expected));
	}

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

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

バブルソート（打ち切り）アルゴリズム

public class OptimizedBubbleSort {

	/**
	 * 最適化バブルソート
	 * 先頭から末尾に向かって隣接する要素を比較して整列させる
	 * ソートの過程で交換が行われなくなった時点で早期に終了する
	 * @param array
	 * @return sortedArray
	 */
	public static int[] bubbleSortWithEarlyStop(int[] array) {
		int[] sortedArray = array.clone();
		int size = sortedArray.length;

		for (int i = 0; i < size - 1; i++) {
			int swapped = 0;
			for (int j = 0; j < size - 1 - i; j++) {
				if (sortedArray[j] > sortedArray[j + 1]) {
					int temp = sortedArray[j];
					sortedArray[j] = sortedArray[j + 1];
					sortedArray[j + 1] = temp;
					swapped++;
				}
			}
			if (swapped == 0) {
				break;
			}
		}
		return sortedArray;
	}
}

完全ランダム配列には、ほぼ効果がない

（テストコード）

	@DisplayName("単純交換ソートと最適化単純交換ソートの交換回数の違いをカウントする")
	@Test
	void testStraightExchangeCount() {
		int[] array1 = { 5, 12, 7, 0, 1, 14, 6, 9, 8, 3, 2, 11, 4, 13, 10, 18, 19, 17, 15, 16 };
		int[] array2 = { 3, 0, 15, 6, 17, 11, 9, 14, 2, 1, 10, 8, 7, 5, 4, 13, 19, 18, 12, 16 };
		int[] array3 = { 10, 14, 6, 3, 4, 18, 15, 12, 1, 17, 19, 2, 8, 5, 11, 9, 16, 0, 7, 13 };
		int[] expected = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19 };

		int[] actual = OptimizedBubbleSort.bubbleSortWithEarlyStop(array1);
		assertThat(actual, is(expected));
		int[] actual2 = OptimizedBubbleSort.bubbleSortWithEarlyStop(array2);
		assertThat(actual2, is(expected));
		int[] actual3 = OptimizedBubbleSort.bubbleSortWithEarlyStop(array3);
		assertThat(actual3, is(expected));

		int[] actual4 = OptimizedBubbleSort.straightExchange(array1);
		assertThat(actual4, is(expected));
		int[] actual5 = OptimizedBubbleSort.straightExchange(array2);
		assertThat(actual5, is(expected));
		int[] actual6 = OptimizedBubbleSort.straightExchange(array3);
		assertThat(actual6, is(expected));
	}

public class OptimizedBubbleSort {

	/**
	 * バブルソート（打ち切りアリ）
	 * 先頭から末尾に向かって隣接する要素を比較して整列させる
	 * ソートの過程で交換が行われなくなった時点で早期に終了する
	 * @param array
	 * @return sortedArray
	 */
	public static int[] bubbleSortWithEarlyStop(int[] array) {
		int[] sortedArray = array.clone();
		int size = sortedArray.length;
		int exchangeCount = 0; // 交換回数のカウント用

		for (int i = 0; i < size - 1; i++) {
			int swapped = 0;
			for (int j = 0; j < size - 1 - i; j++) {
				if (sortedArray[j] > sortedArray[j + 1]) {
					int temp = sortedArray[j];
					sortedArray[j] = sortedArray[j + 1];
					sortedArray[j + 1] = temp;
					swapped++;
					exchangeCount++; // 交換が行われたらカウントを増やす
				}
			}
			if (swapped == 0) {
				break;
			}
		}
		System.out.println("打ち切りアリの交換回数: " + exchangeCount); // 交換回数を出力
		return sortedArray;
	}

	/**
	 * バブルソート（単純交換ソート）
	 * 先頭から末尾に向かって隣接する要素を比較して整列させる
	 * @param array
	 * @return sortedArray
	 */
	static int[] straightExchange(int[] array) {
		int[] sortedArray = array.clone();
		int size = sortedArray.length;
		int exchangeCount = 0; // 交換回数のカウント用

		for (int i = 0; i < size - 1; i++) {
			for (int j = 0; j < size - 1 - i; j++) {
				if (sortedArray[j] > sortedArray[j + 1]) {
					int temp = sortedArray[j];
					sortedArray[j] = sortedArray[j + 1];
					sortedArray[j + 1] = temp;
					exchangeCount++; // 交換が行われたらカウントを増やす
				}
			}
		}
		System.out.println("打ち切り無しの交換回数: " + exchangeCount); // 交換回数を出力
		return sortedArray;
	}
}

結果

打ち切りアリの交換回数: 53
打ち切りアリの交換回数: 73
打ち切りアリの交換回数: 98
打ち切り無しの交換回数: 53
打ち切り無しの交換回数: 73
打ち切り無しの交換回数: 98

完全ランダムな配列では特に最適化されてませんでした。