계수 정렬

 

계수 정렬: 범위 조건이 있는 경우에 한해 빠른 정렬 알고리즘

 

크기를 기준으로 개수를 세는 알고리즘이며, 모든 데이터에 한번씩만 접근하면 된다는 점에서 효율적이라 할 수 있음.

 

그러나, 데이터의 크기가 한정되어 있을 때에 한해서만 사용할 수 있음.

 

시간 복잡도: O(N)

앞에서 차례대로 데이터를 하나씩 읽어 주기만하면 되므로 N에 비례하는 시간 복잡도를 가진다.

 

#include <stdio.h>

int main() {
	int temp;
	int count[5]; // 범위 기준 : 1~5
	int arr[30] = {
		1, 3, 2, 4, 3, 2, 5, 3, 1, 2,
		3, 4, 4, 3, 5, 1, 2, 3, 5, 2,
		3, 1, 4, 3, 5, 1, 2, 1, 1, 1
	};
	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);
			}
		}
	}
}