明解 Javaによるアルゴリズムとデータ構造　6-3_単純選択ソート

コンピュータ Java 本

6-3 単純選択ソート straight selection sort

最小要素を先頭に、2番めに小さい要素を先頭から2番目に移動する、を繰り返すアルゴリズム

  1. 未ソート部から最小のキーを持つ a[min] を選択
  2. a[min] と、未ソート部の先頭要素を交換
  • 離れた要素を交換する可能性があるため、安定ではない
  • 比較回数 : \displaystyle \sum_{k=1}^{n-1} \(n - k)} = \frac{(n-1)n}{2}
    • 1パスにつき、最小要素1つに、その他の要素を n - (現パス数) 回ぶつけて最小判定。それを n - 1 パス実施
ソースコード(途中経過表示板)
import java.util.Scanner;

class SelectionSort {
	static void swap(int[] a, int idx1, int idx2) {
		int t = a[idx1];
		a[idx1] = a[idx2];
		a[idx2] = t;
	}

	static void selectionSort(int[] a, int n) {
		for (int i = 0; i < n - 1; i++) {
			System.out.println("パス: " + (i + 1));
			int min = i;
			for (int j = i + 1; j < n; j++) { //  j -> 交換検討対象のインデックス
				if (a[j] < a[min]) {
					// ソート前状態の表示
					for (int k = 0; k < n; k++) {
						if (k == min) {
							System.out.printf("%2d* ", a[k]); // "*" -> 現時点での最小要素
						}  else if (k == j) {
							System.out.printf("%2d+ ", a[k]); // "+" -> 比較の結果新たに最小となった要素
						}	else {
							System.out.printf("%2d  ", a[k]);
						}
					}
					System.out.println();
					min = j;
					
				} else {
					// ソート前状態の表示
					for (int k = 0; k < n; k++) {
						if (k == min) {
							System.out.printf("%2d* ", a[k]);
						}  else if (k == j) {
							System.out.printf("%2d- ", a[k]); // "-" -> 比較の結果最小にならなかった要素
						}	else {
							System.out.printf("%2d  ", a[k]);
						}
					}
					System.out.println();
				}
			}
			swap(a, i, min);
			
			// ソート後状態の表示
			for (int e : a) {
				System.out.printf("%2d  ", e);
			}
			System.out.println();
		}
	}

	public static void main(String[] args) {
		Scanner stdIn = new Scanner(System.in);

		System.out.println("単純選択ソート");
		System.out.print("要素数: ");
		int nx = stdIn.nextInt();
		;
		int[] x = new int[nx];

		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "]:");
			x[i] = stdIn.nextInt();
		}

		selectionSort(x, nx);

		System.out.println("昇順にソートしました");
		for (int i = 0; i < nx; i++) {
			System.out.println("x[" + i + "] = " + x[i]);
		}
	}
}
単純選択ソート
要素数: 4
x[0]:
4
x[1]:
3
x[2]:
2
x[3]:
1
パス: 1
 4*  3+  2   1  
 4   3*  2+  1  
 4   3   2*  1+ 
 1   3   2   4  
パス: 2
 1   3*  2+  4  
 1   3   2*  4- 
 1   2   3   4  
パス: 3
 1   2   3*  4- 
 1   2   3   4  
昇順にソートしました
x[0] = 1
x[1] = 2
x[2] = 3
x[3] = 4
明解 Javaによるアルゴリズムとデータ構造

明解 Javaによるアルゴリズムとデータ構造