計数ソート [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オリジン配列を扱うので、添え字やループカウンタの書き間違いには注意したいところです。