Javaでバブルソート

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

ja.wikipedia.org

長さ n の数列をバブルソートでソートするとき、

・0 ~ n-2 番目までの最大値を n-1 番目にもってくる
・0 ~ n-3 番目までの最大値を n-2 番目にもってくる
　（中略）
・0 ~ 0 番目までの最大値を 1 番目にもってくる

という流れで処理していきます。1番大きい値、2番目に大きい値......と右側から順に確定させていくイメージです。

バブルソートを実装するにあたっては、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());
		
		int count = 0;
		for (int i=0; i<n-1; i++) {
			for (int j=0; j<n-i-1; j++) {
				if (list.get(j) > list.get(j+1)) {
					Collections.swap(list, j, j+1);
					count++;
				}
			}
		}
		
		for (int i=0; i<n; i++) {
			System.out.print((i==0?"":" ")+list.get(i));
		}
		System.out.println();
		System.out.println(count);
		
	}
}