5. 계수 정렬 (Counting Sort)

범위 조건이 있는 경우에 굉장히 빠른 알고리즘

시간 복잡도: O(N)

단순하게 '크기를 기준으로' 세는 알고리즘

 

예시) 숫자는 1에서 5사이의 정수

1 3 2 4 3 2 5 3 1 2 3 4 4 2 5 1 2 3 5 2 3 1 4 3 5 2 1 1 1

1이 몇 개인지, 2가 몇 개인지.... 5가 몇 개인지 셈

 

#include <stdio.h>

int main(void){
	
	int temp;
	int count[5];
	int arr[30] = {
		1, 3, 3, 5, 2, 3, 4, 2, 4, 4, 
		5, 3, 4, 2, 1, 1, 2, 3, 5, 3,
		2, 4, 4, 1, 2, 3, 3, 2, 5, 3};
	
	// 배열 초기화 
	for(int i = 0; i<5; i++){
		count[i] = 0;
	}
		
	for(int i = 0; i<30; i++){
		count[arr[i]-1]++;
	}
	
	for(int i = 0; i<5; i++){
		if(count[i] != 0){
			for(int j = 0; j<count[i]; j++){
				printf("%d ", i+1);
			}
		}
	}
	
	return 0;
}