계수 정렬(counting sort)

<특징>

1. 데이터값은 양수여야 가능

2.  각각의 데이터가 몇 번 등장했는지 세는 방식이다. 

따라서 가장 큰 데이터의 크기로 배열을 만들어야 한다. 

--> 많은 메모리 공간을 필요로  함

 ex) 데이터가 5개 존재하는데 각각 0, 3, 2, 1, 1000000 이라면?

3. 데이터 간 비교를 하지 않으므로 시간 복잡도는 O(N) 이다.

  수의 범위가 작다면 계수 정렬을 쓰는게 유리하다.

---

<원리>

데이터들이 저장된 배열에서 각 숫자가 몇번 나오는지 세는 방식이다.

[3,4,1,2,4,6,1] 이라는 배열이 있다고 하자.

1 : 2개
2 : 1개
3 : 1개
4 : 2개
6 : 1개

그렇다면, 1부터 6까지 갯수대로 나열해보자.

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

---

<구현>

void countingsort(int data[], int size)
{
	int temp[10001] = { 0, }; //수의 범위가 10000까지라고 가정하면 배열의 크기는 10001, 
                              //모든 인덱스 0으로 초기화
	int count;
	for (int i = 0; i < size; i++) {
		count = data[i];
		temp[count]++; //수에 해당하는 인덱스에 값을 1씩 증가하며 해당 데이터의 빈도수를 기록
	}
	for (int i = 0; i < 10001; i++) {
		for (int j = 0; j < temp[i]; j++) {/*배열에 저장된 값이 0이 아니라면 
                                            저장된 값의 횟수만큼 순서대로 숫자 출력*/
			printf("%d\n", i);
		}
	}
}

배열로 저장된 데이터가 아니라 입력받은 데이터들이라면 바로 정렬하는 것도 가능.

int main() {
	int N=5; //정렬할 데이터의 개수를 5개라고 가정
	int count; 
	int temp[10001] = { 0, };
	for (int i = 0; i < N; i++) {
		scanf("%d", &count); //데이터 입력받아서 
		temp[count]++; //바로 해당 인덱스에 빈도수 기록
	
	for (int i = 0; i < 10001; i++) {
		for (int j = 0; j < temp[i]; j++) {
			printf("%d\n", i);
		}
	}
	return 0;
}