[알고리즘] 계수 정렬 (Counting Sort)

1. 메모리 신경 안쓴 버전

public class CountingSort {

	public static void countingSort(int[] a, int[] b) {
		int[] c = new int[10001];

		for (int i = 0; i < a.length; i++) {
			c[a[i]]++;
		}
		for (int i = 1; i < c.length; i++) {
			c[i] = c[i] + c[i - 1];
		}
		for (int i = a.length - 1; i >= 0; i--) {
			b[--c[a[i]]] = a[i];
		}
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] input = new int[n];
		int[] output = new int[n];

		for (int i = 0; i < n; i++) {
			input[i] = Integer.parseInt(reader.readLine());
		}

		countingSort(input, output);

		StringBuffer sb = new StringBuffer();
		for (int a : output) {
			sb.append(a).append("\n");
		}

		writer.write(sb.toString());
		writer.flush();
		writer.close();
		reader.close();
	}

}

2. 메모리 고려한 버전 ( 다만 배열 삽입된 모양이 깔끔하지 않음.. )

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class CountingSort {

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

		int n = Integer.parseInt(reader.readLine());

		int[] input = new int[10001];

		for (int i = 0; i < n; i++) {
			input[Integer.parseInt(reader.readLine())]++;
		}

		for (int i = 0; i < 10000 + 1; i++) {
			if (input[i] != 0) {
				for (int j = 0; j < input[i]; j++) {
					writer.write(String.valueOf(i));
					writer.newLine();
				}
			}
		}
		writer.close();
		reader.close();
	}

}