정렬 (12) - 계수 정렬 (Counting Sort)

1. 알고리즘 개요

• 입력의 개수가 아닌 크기에 영향을 받는 정렬 알고리즘

• 단순하게 해당 데이터가 몇개인지 세주는 것 만으로 정렬의 효과를 볼 수 있음

• 시간 복잡도 : $O(n)$으로 가장 빠르나, 최대값의 크기가 큰 경우 매우 비효율적임.

 

2. Counting Sort

• {1, 3, 2, 2, 1, 2, 2, 3, 5, 4, 4, 5}와 같은 배열이 있을 때 기존 방식들로는 size = 12이기 때문에 size 12의 영향을 받지만, 이 경우 최대값이 5이고, 최대값 5에 대한 영향만 받게 됨.

• 가장 먼저 최댓값(5)의 사이즈로 배열을 만듬 (따라서 최대값이 얼마인지 알고 있어야 함)

• 입력데이터를 순회하면서, 위에서 만든 배열에 기록함.

• 기록한 배열을 순회하면서 배열의 원소들을 체크된 개수만큼 출력함

• 값이 큰 수가 있을 경우 (e.g. {1, 2, 2, 1, 100, 2} 와 같은) 3 ~ 99까지는 없는 수이지만 count array 공간을 생성해야하기 때문에 수가 크면 매우 비효율적임. 때문에 입력데이터가 작은 범위 내에서 한정적인 경우에만 사용하는 것이 좋음.

 

 

3. 소스 코드

#include<stdio.h>
# define max 30

void counting_sort(int *arr, int size){
	
	int count[max];
	for(int i = 0; i < max ; i++){
		count[i] = 0; // 초기화 
	}
	
	for(int i = 0 ; i < size ; i++){
		int val = arr[i];
		count[val]++; // 개수 세기 
	}
	
	for(int i = 0 ; i < max ; i++){
		for(int j = 0 ; j < count[i] ; j++){
			printf("%d ", i);
		}		
	}	
}

int main(){
	
	int arr[] = {1,3,2,4,1,23,12,12,3,12,3,23,23};	
	int size = sizeof(arr)/sizeof(arr[0]);
	
	counting_sort(arr, size);
	
	return 0;
}

 

4. Reference