Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

計数ソート [ALDS1_6_A : Counting Sort]

計数ソート | アルゴリズムとデータ構造 | Aizu Online Judge

AIZU ONLINE JUDGEの問題です。


package Blog;

import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);

	public static void main(String[] args) {
		int n = sc.nextInt();
		int[] ar = new int[n+1];
		int[] count = new int[10001];
		for (int i=1; i<n+1; i++) {
			int temp = sc.nextInt();
			ar[i] = temp;
			count[temp]++;
		}
		
		for (int i=1; i<10001; i++) {
			count[i] = count[i] + count[i-1];
		}

		int[] ans = new int[n+1];
		for (int i=n; i>=1; i--) {
			ans[count[ar[i]]] = ar[i];
			count[ar[i]]--;
		}
		
		StringBuilder sb = new StringBuilder();
		sb.append(ans[1]);
		for (int i=2; i<n+1; i++) sb.append(" "+ans[i]);
		out.println(sb);
	}
}

面白いソート方法だなと思いました。

流れとしては、

①ソート対象となる配列(A)を用意
②Aの各要素について、それぞれ何回登場するか数え、別の配列(B)に記録する
③Bを累積和にかける
④Bを参考にして、Aの要素をさらに別の配列(C)に配置していく

といった感じでしょうか。配列を三本も使っていて、一見すると効率は悪そうです。

競プロでよく使う書き方、

・カウント用配列[要素]++;

というのが出てきました。

1オリジン配列を扱うので、添え字やループカウンタの書き間違いには注意したいところです。