[알고리즘] 카운팅정렬 CountingSort

시간복잡도가 n이나, 나오는 수가 한정되어 있을때 사용하는게 좋다.

#include <stdio.h>

int main(){

	int n = 20;
	int arr[20] = { 1,3,2,4,3,2,1,5,4,4,3,2,3,4,5,5,1,1,1 };
	// 특정 경우의 수일때, nlogn 정렬들 (퀵소트, 힙소트, 머지소트) 보다 강력하다
	// 시간복잡도가 n이 나옴
	// 조건은 보통 "몇 이하의 자연수들로만 나올때"


	int count[6] = { 0, };
	// 카운트 배열의 경우 초기화는 반드시 필수 (memset이나 위 명령어 사용);

	for (int i = 0; i < n; i++){
		count[arr[i]]++;
		// 해당 인덱스에 값을 늘려준다 (카운팅함)
	}

	// 출력시 아래와 같이 한다.
	for (int i = 1; i <= 5; i++){
		while (count[i]--){
			printf("%d ", i);
		}
	}



	return 0;
}