Javaで学ぶアルゴリズム -双方向バブルソート

双方向バブルソート

シェーカーソート (英: shaker sort) は、ソートのアルゴリズムの一つ。バブルソートを、効率がよくなるように改良したもの。別名は、双方向バブルソート、改良交換法。
バブルソートではスキャンを一方向にしか行わないのに対し、シェーカーソートでは交互に二方向に行う。

実行環境

• JUnit 5
• Java 8

テストコード

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

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

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

		int[] actual = ShakerSort.shakerSort(array);
		assertThat(actual, is(expected));
	}

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

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

双方向バブルソートアルゴリズム

ShakerSort.java

public class ShakerSort {

	/**
	 * 双方向バブルソート（シェーカーソート / カクテルソート）
	 * リストの両端から交互に、小さい値を前方に、大きい値を後方に移動させる
	 * @param array
	 * @return sortedArray
	 */
	static int[] shakerSort(int[] array) {
		int[] sortedArray = array.clone();
		boolean swapped = true;
		int start = 0;
		int end = sortedArray.length;

		while (swapped) {
			swapped = false;
			// 左側から右側へ
			for (int i = start; i < end - 1; i++) {
				if (sortedArray[i] > sortedArray[i + 1]) {
					int temp = sortedArray[i];
					sortedArray[i] = sortedArray[i + 1];
					sortedArray[i + 1] = temp;
					swapped = true;
				}
			}
			// もし交換が行われなければソート完了！
			if (!swapped) {
				break;
			}
			swapped = false;
			end--;

			// 右から左へ
			for (int i = end - 1; i > start; i--) {
				if (sortedArray[i] < sortedArray[i - 1]) {
					int temp = sortedArray[i];
					sortedArray[i] = sortedArray[i - 1];
					sortedArray[i - 1] = temp;
					swapped = true;
				}
			}
			start++;
		}
		return sortedArray;
	}
}

ほんまにちょっと早いんか？

ほんまにちょっと早かった。（約0.014秒）

比較結果

# 平均
- Bubble Sort Time (ns): 67847120
- Shaker Sort Time (ns): 53846810

# 10回やった結果
[0]Bubble Sort Time (ns): 71186800
[0]Shaker Sort Time (ns): 55984600
[1]Bubble Sort Time (ns): 67625300
[1]Shaker Sort Time (ns): 51022800
[2]Bubble Sort Time (ns): 66963800
[2]Shaker Sort Time (ns): 62410100
[3]Bubble Sort Time (ns): 67698600
[3]Shaker Sort Time (ns): 49956600
[4]Bubble Sort Time (ns): 67553300
[4]Shaker Sort Time (ns): 51271400
[5]Bubble Sort Time (ns): 67473500
[5]Shaker Sort Time (ns): 50572100
[6]Bubble Sort Time (ns): 67864000
[6]Shaker Sort Time (ns): 50937000
[7]Bubble Sort Time (ns): 67579300
[7]Shaker Sort Time (ns): 51001200
[8]Bubble Sort Time (ns): 68599200
[8]Shaker Sort Time (ns): 51434300
[9]Bubble Sort Time (ns): 65927400
[9]Shaker Sort Time (ns): 63878000

パフォーマンス比較用に加工した ShakerSort.java

import java.util.Random;

public class ShakerSort {

	public static void main(String[] args) {
		for (int i = 0; i < 10; i++) {
			int[] data = generateRandomArray(10000, 100000); // 10000個のランダムな要素を持つ配列を生成

			// 単純なバブルソート
			int[] dataForStraightExchange = data.clone();
			long startTime = System.nanoTime();
			straightExchange(dataForStraightExchange);
			long endTime = System.nanoTime();
			long bubbleSortTime = endTime - startTime;

			// 双方向バブルソート
			int[] dataForShakerSort = data.clone();
			startTime = System.nanoTime();
			shakerSort(dataForShakerSort);
			endTime = System.nanoTime();
			long cocktailSortTime = endTime - startTime;

			// Output the times
			System.out.println("[" + i + "]Bubble Sort Time (ns): " + bubbleSortTime);
			System.out.println("[" + i + "]Shaker Sort Time (ns): " + cocktailSortTime);
		}
	}

	/**
	 * ランダムな ${size} 個の要素（整数）を持つ配列を生成する
	 * @param size
	 * @param bound: 値の範囲
	 * @return array
	 */
	static int[] generateRandomArray(int size, int bound) {
		Random random = new Random();
		int[] array = new int[size];
		for (int i = 0; i < size; i++) {
			array[i] = random.nextInt(bound);
		}
		return array;
	}

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

		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;
				}
			}
		}
	}

	/**
	 * 双方向バブルソート（シェーカーソート / カクテルソート）
	 * リストの両端から交互に、小さい値を前方に、大きい値を後方に移動させる
	 * @param array
	 */
	static void shakerSort(int[] array) {
		int[] sortedArray = array.clone();
		boolean swapped = true;
		int start = 0;
		int end = sortedArray.length;

		while (swapped) {
			swapped = false;
			// 左側から右側へ
			for (int i = start; i < end - 1; i++) {
				if (sortedArray[i] > sortedArray[i + 1]) {
					int temp = sortedArray[i];
					sortedArray[i] = sortedArray[i + 1];
					sortedArray[i + 1] = temp;
					swapped = true;
				}
			}
			// もし交換が行われなければソート完了！
			if (!swapped) {
				break;
			}
			swapped = false;
			end--;

			// 右から左へ
			for (int i = end - 1; i > start; i--) {
				if (sortedArray[i] < sortedArray[i - 1]) {
					int temp = sortedArray[i];
					sortedArray[i] = sortedArray[i - 1];
					sortedArray[i - 1] = temp;
					swapped = true;
				}
			}
			start++;
		}
	}
}