選択ソート

選択ソート（英: selection sort）は、ソートのアルゴリズムの一つ。配列から最小値を探し、配列の先頭要素と入れ替えていくことで並べ替える。

実行環境

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

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

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

		int[] actual = SelectionSort.selectionSort(array);
		assertThat(actual, is(expected));
	}

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

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

単純選択ソートアルゴリズム

public class SelectionSort {

	/**
	 * 選択ソート
	 * 配列の中から最小値を見つけて先頭に持ってくる、を繰り返す
	 * @param array
	 * @return sortedArray
	 */
	public static int[] selectionSort(int[] array) {
		int[] sortedArray = array.clone();
		for (int i = 0; i < sortedArray.length; i++) {
			int min = i;
			for (int j = i + 1; j < sortedArray.length; j++) {
				if (sortedArray[j] < sortedArray[min]) {
					min = j;
				}
			}
			int tmp = sortedArray[i];
			sortedArray[i] = sortedArray[min];
			sortedArray[min] = tmp;
		}
		return sortedArray;
	}
}

選択ソートは安定ではない

安定ではないとはつまり、ソートの前後で「同一のキーを持つ要素の順番が維持されない」ということです。

SelectionSort.java（選択ソートが安定ではないことを示すプログラム）

public class SelectionSort {

	public static void main(String[] args) {
		Element[] array = {
				new Element(1, "0"),
				new Element(1, "1"),
				new Element(1, "2"),
				new Element(2, "3"),
				new Element(1, "4"),
				new Element(1, "5"),
				new Element(1, "6"),
				new Element(1, "7"),
				new Element(2, "8"),
				new Element(1, "9")
		};

		printArray("Before Sorting:", array);
		selectionSort(array);
		printArray("After Sorting:", array);
	}

	/**
	 * 選択ソート
	 * 配列の中から最小値を見つけて先頭に持ってくる、を繰り返す
	 * @param array
	 */
	public static void selectionSort(Element[] array) {
		for (int i = 0; i < array.length; i++) {
			int min = i;
			for (int j = i + 1; j < array.length; j++) {
				if (array[j].key < array[min].key) {
					min = j;
				}
			}
			Element tmp = array[i];
			array[i] = array[min];
			array[min] = tmp;
		}
	}

	private static void printArray(String message, Element[] array) {
		StringBuilder keys = new StringBuilder();
		StringBuilder values = new StringBuilder();

		for (Element e : array) {
			keys.append("[").append(e.key).append("]");
			values.append("[").append(e.value).append("]");
		}

		System.out.println(message);
		System.out.println("-------------------------------");
		System.out.println(keys);
		System.out.println(values);
		System.out.println("-------------------------------\n");
	}
}

Element.java

class Element {

	int key;
	String value;

	Element(int key, String value) {
		this.key = key;
		this.value = value;
	}
}

ソート前後をキャプチャしているのが以下の出力なのですが、キーが2の要素に着目すると、valueの順番が入れ替わっちゃってます！

実行結果

Before Sorting:
-------------------------------
[1][1][1][2][1][1][1][1][2][1]
[0][1][2][3][4][5][6][7][8][9]
-------------------------------

After Sorting:
-------------------------------
[1][1][1][1][1][1][1][1][2][2]
[0][1][2][4][5][6][7][9][8][3]
-------------------------------