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

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

 

계수 정렬은 데이터의 키에 따라 객체를 수집 정렬 하는 정렬 알고리즘이다.

• 비교 연산을 하지 않는 정렬 알고리즘이다.
• 키의 다양성이 데이터의 수보다 상당히 크지 않은 상황에서 유용하다.
• O(n)의 시간 복잡도를 가진다.
• 데이터 중 가장 작은 값과 가장 큰 값을 기준으로 하는 공간 크기가 필요하다. (1~10의 경우 10개의 공간이 필요하지만 1과 10000이 들어 있는 데이터에서는 10000의 배열 크기가 필요하다.)
• 특정한 값이 몇번 등장했는지에 따라 정렬을 수행한다.
• 계수를 다 카운팅 한 후에 앞에서 부터 차례대로 배열에 넣는다.

 

정렬 과정

10000개의 공간에 1 ~ 10까지의 정수가 무작위로 들어가 있다고 가정한다.

최솟값 최댓값을 알고 있을 때, 각 정수를 카운팅하기 위한 정수 배열을 만든다.

정수는 1 ~ 10까지의 범위를 가지고 있기 때문에 10개의 공간이 필요하다.

데이터가 들어있는 배열 0번 인덱스 부터 9999번 인덱스까지 순회하면서 각 정수를 카운팅한다.

0번 인덱스 : 정수 1의 개수

1번 인덱스 : 정수 2의 개수

2번 인덱스 : 정수 3의 개수

3번 인덱스 : 정수 4의 개수

4번 인덱스 : 정수 5의 개수

5번 인덱스 : 정수 6의 개수

6번 인덱스 : 정수 7의 개수

7번 인덱스 : 정수 8의 개수

8번 인덱스 : 정수 9의 개수

9번 인덱스 : 정수 10의 개수

 

위 표와 같이 데이터들의 카운팅이 완료되면 계수를 위한 첫 번째 인덱스부터 카운팅된 수만큼 삽입한다.

arr[0] ~ arr[999] : 1 삽입

arr[1000] ~ arr[2999] : 2삽입

------------------------------------

arr[9000] ~ arr[9999] : 10 삽입

 

// 슈도 코드

CountingSort()
{
	int arr[10000]; // { 1~10까지 무작위 }
    int counting[10]; // 계수
    
    for( i = 0 ~ arr.length )
    	counting[arr[i]-1]++;
        
    int index = 0;
    for(i = 0 ~ counting.length)
		for(j = 1 ~ counting[])
        	arr[index++] = i+1;
}