[Java] Counting Sort(카운팅 정렬)

Counting Sort는 일반적인 정렬 알고리즘과 달리 데이터를 서로 비교하지 않고, 데이터의 값을 카운팅 하여 정렬하는 알고리즘입니다. 시간 복잡도는 O(n)인데, 빠른 정렬 알고리즘으로 알려져 있는 Quick Sort, Merge Sort, Heap Sort 등의 시간 복잡도가 O(nlogn)라는 것을 생각하면 Counting Sort의 속도가 엄청나다는 것을 알 수 있습니다.

 

그럼 왜 Counting Sort는 사용하지 않는 것일까요?

 

Counting Sort는 정렬 할 배열의 최댓값의 +1만큼 새로운 카운팅 배열을 생성해줘야 하는데, 수의 범위가 크다면 메모리를 많이 낭비하기 때문에 자주 사용하지 않습니다.

 

 

과정

정렬할 배열

1. 먼저 정렬할 배열의 데이터의 최댓값의 +1 크기의 카운팅 배열을 생성합니다.

array [0] = 4 이므로 counting_array [4]의 값을 1 증가

array [1] = 5 이므로 counting_array [5]의 값을 1 증가

...

array [15] = 5 이므로 counting_array [5]의 값을 1 증가

 

 

 

2. 카운팅 배열의 값을 누적합으로 변환시킨다.

예를 들어 카운팅 배열이 [1, 3, 2, 1, 1, 2]라면

[1, 4, 2, 1, 1, 2]

[1, 4, 6, 1, 1, 2]

[1, 4, 6, 7, 1, 2]

[1, 4, 6, 7, 8, 2]

[1, 4, 6, 7, 8, 10]]

해당 인덱스의 값이 (자기 자신의 값 + 이전의 인덱스의 값)이 된다.

 

 

 

3. 카운팅 배열의 값의 -1은 정렬할 배열의 새로운 위치를 의미한다.

array [15] = 5의 값은 counting_array [5] - 1 위치의 인덱스로 이동

array [14] = 7의 값은 counting_array [7] - 1 위치의 인덱스로 이동

...

array [0] =4의 값은 counting_array [4] - 1 위치의 인덱스로 이동

 

이때, 실수할 수 있는 부분이 있는데 counting_array의 - 1은 중첩이 되면서 저장되어야 합니다.

 

 

 

완성된 코드

package CountingSort;

public class CountingSort {

	public static void main(String[] args) {
		int[] array = {4, 5, 3, 7, 2, 1, 0, 6, 1, 3, 4, 2, 1, 6, 7, 5}; // 정렬할 배열
		int[] counting_array = new int[8]; // 카운팅 배열
		int[] result = new int[array.length];
		
		for(int i = 0 ; i < array.length ; i++) {
			counting_array[array[i]]++; // 과정 1번
		}
		
		for(int i = 1 ; i < counting_array.length ; i++) {
			counting_array[i] += counting_array[i-1]; // 과정 2번
		}
		
		for(int i = array.length - 1 ; i >= 0 ; i--) {
			result[--counting_array[array[i]]] = array[i]; // 과정 3번
		}
		
		for(int i = 0 ; i < result.length ; i++) {
			System.out.print(result[i]);			
		}
	}

}

위의 과정에서 알 수 있듯이 Couting Sort는 특정 타입에 한정되어 있을 뿐만 아니라, 수의 범위에 따라 메모리의 낭비가 천차만별이기 때문에 사용처가 극히 한정적입니다.

 

하지만 시간 복잡도가 O(n)이기 때문에, 수의 범위가 크지 않다면 대부분의 알고리즘 문제에서의 시간 초과는 피할 수 있습니다.