계수 정렬 (Counting Sort)

소개

• 요소 값들끼리 서로 비교하지 않고 정렬하는 알고리즘이다.
• 배열 내 최대 값 + 1 만큼의 길이 배열이 필요하기 때문에 메모리가 낭비될 수 있다.
• 애니메이션 : URL

 

 

 

과정

1. 먼저 배열 내에 원소 값들의 갯수를 저장하는 카운팅 배열 (Counting Array) 를 만든다.

 

2. Counting Array (c[])의 요소들에 대해서 직전 요소들의 값을 더해준다.

 

3. 입력 배열과 동일한 크기의 출력 배열 (b[])을 만들고, 입력 배열의 역순으로 출력 배열에 요소들을 채워 넣어준다.

• 여기서 우리는 두 값을 비교하는 과정 없이 정렬이 수행되는 것을 알 수 있다.

 

 

코드

public static void main(String[] args) {
	final int MAX = 5;
	int[] nums = { 1, 0, 1, 5, 4, 3, 1, 4, 5, 2, 1 };
	int len = nums.length;
	int[] counts = new int[MAX + 1];
	int[] sorted = new int[len];

	for (int i = 0; i < len; ++i) {
		++counts[nums[i]];
	}

	for (int i = 1; i <= MAX; ++i) {
		counts[i] += counts[i - 1];
	}

	for (int i = len - 1; i >= 0; --i) {
		sorted[counts[nums[i]]] = nums[i];
		--counts[nums[i]];
	}
}

 

 

결과

• 100은 아직 정렬되지 않은 공간을 의미한다.

 

 

계산 복잡도

Time Complexity : 배열을 모두 훑어야 하므로 \(O(N)\) 이다.

• Best : \(O(N)\)
• Average : \(O(N)\)
• Worst : \(O(N)\)

Space Complexity : 배열내 요소의 최대 값을 \(K\) 라고 할 때, \(K + 1\) 길이를 가진 Counting Array가 필요하므로 \(O(K)\) 이다.