選択ソート
選択ソート（英: 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]
-------------------------------