[Data Structure] 카운팅 정렬

카운팅 정렬은 배열 원소끼리 비교하는게 아닌 인덱스 위치를 갖고 위치를 찾아가는 방법이다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {	
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int n = Integer.parseInt(br.readLine());
		
		int[] arr = new int[10001];	// 수의 범위 0~10000
		for(int i = 0; i < n; i++) {	// 입력 횟수
			arr[Integer.parseInt(br.readLine())]++;
		}
		
		for(int i = 0; i < arr.length; i++) {
			while(arr[i]-- > 0) {
				bw.write(i + "\n");
			}
		}
		
		bw.flush();
		bw.close();
	}		
}

• 카운팅 정렬은 시간복잡도가 O(n)으로 엄청 빠른 정렬 방법이다.
• 하지만 실사용에서는 많이 사용되지 않는다. 그 이유로는 입력값의 범위에 따라 메모리가 결정된다는 점 때문이다.
• 입력되는 값의 범위가 작고, 입력의 개수가 많을 땐 효율적이지만 값의 범위가 크고 입력의 개수가 작을 땐 비효율적이다.
• 입력되는 값의 범위가 크면 입력 개수가 작아도 그만큼(값의 범위)의 메모리 공간을 유지하고 있어야 해서 보통은 쓰지 않는다.
• 위와같은 안정성 문제로 쓰이지 않고 보통 Tim Sort나 QuickSort를 사용한다.