Javaで挿入ソート

本記事では挿入ソート（Insertion Sort）のアルゴリズムと実装を勉強します。

ja.wikipedia.org

挿入ソートのアルゴリズムはとても単純……なはずなのですが、Wikipedia や AIZU ONLINE JUDGE にあったサンプルコードがよく理解できませんでした。そのため、挿入ソートとほとんど同じ動作をする別のアルゴリズム、になってしまっている可能性があります。ご了承ください。個人的には、本記事で紹介するコードのほうが簡潔でわかりやすいと思っています。

挿入ソートを実装するにあたっては、AIZU ONLINE JUDGE の以下の問題を使用します。

judge.u-aizu.ac.jp

与えられた数列を挿入ソートでソートする過程を出力する問題です。

import java.util.*;

class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String args[]) {
		
		int n = sc.nextInt();
		ArrayList<Integer> list = new ArrayList<>();
		for (int i=0; i<n; i++) list.add(sc.nextInt());
		
		for (int i=0; i<n; i++) {

			for (int j=0; j<i; j++) {
				if (list.get(i) < list.get(j)) {
					Collections.swap(list, i, j);
				}
			}

			for (int j=0; j<n; j++) {
				System.out.print((j==0?"":" ")+list.get(j));
			}
			System.out.println();
			
		}
		
	}
}

数列の i 番目の値について、0 番目から i-1 番目まで探索し、i 番目の値より大きい値が見つかった場合には、その値と i 番目の値を交換します。この処理を i=0 から i=n-1 まで順に適用することで、ソートが完了します。