<카운팅 정렬>

입력되는 정수의 배열의 범위가 보장될때, 유용한 아주 간단하고 효율적인 좋은 알고리즘.

package 정렬알고리즘;

import java.io.*;

//운팅 정렬(Counting Sort)은 정수 배열을 정렬하는 비교 없이 선형 시간에 수행되는 안정적인 정렬 알고리즘입니다
// 알고리즘은 입력 배열의 범위가 제한되어 있을 때 특히 유용합니다
public class 카운팅정렬 {

	public static void main(String[] args) throws IOException {
		int[] range = new int[10001];
		 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        int N = Integer.parseInt(br.readLine());
 
        for (int i = 0; i < N; i++) {
            // 해당 인덱스의 값을 1 증가
            range[Integer.parseInt(br.readLine())] ++;
        }
 
        br.close();
 
        StringBuilder sb = new StringBuilder();
 
        // 0은 입력범위에서 없으므로 1부터 시작
        for(int i = 1; i < 10001; i++){
            // i 값이 개수가 0 이 될 때 까지 출력 (빈도수를 의미)
            while(range[i] > 0){
                sb.append(i).append('\n');
                range[i]--;
            }
        }
        System.out.println(sb);
		

	}

}