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

バブルソート

バブルソート（英: bubble sort）は、隣り合う要素の大小を比較しながら整列させるソートアルゴリズム。
アルゴリズムが単純で実装も容易である一方、最悪時間計算量は O(n2) と遅いため、一般にはマージソートやヒープソートなど、より最悪時間計算量の小さな（従って高速な）方法が利用される。

実行環境

• JUnit 5
• Java 8

テストコード

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

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

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

		int[] actual = StraightExchangeSort.straightExchange(array);
		assertThat(actual, is(expected));
	}

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

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

バブルソートアルゴリズム

StraightExchangeSort.java

// バブルソート（単純交換ソート）
public class StraightExchangeSort {

	/**
	 * 先頭から末尾に向かって隣接する要素を比較して整列させる
	 * @param array
	 * @return sortedArray
	 */
	static int[] 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;
				}
			}
		}
		return sortedArray;
	}

	/**
	 * 末尾から先頭に向かって隣接する要素を比較して整列させる
	 * @param array
	 * @return sortedArray
	 */
	static int[] straightExchangeReverse(int[] array) {
		int[] sortedArray = array.clone();
		int size = sortedArray.length;

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