[정렬] 계수정렬 ( Counting Sort )

void countSort(vector<int>& v, int n) {
	vector<int> count(30, 0);// count 초기화
	int i;
	for (i = 0;i < n;i++) {
		count[v[i]]++;
	}
	for (i = 0;i < 30;i++) {
		for (int j = 0;j < count[i];j++) {
			printf("%d ", i);
		}
	}
}

제자리성 : 제자리 x

 

안정성 : 안정

(순서대로 배치)

 

시간 복잡도

최악 시간 복잡도 = O(n)

 

알고리즘 

1. count 배열 초기화

2. 배열을 순회하여 배열의 인덱스 값에 해당하는 count index 에 ++

3. 이중 반복문 사용하여 count에 할당된 값만큼 index 값 출력

 

특정 배열에 대해 아주 빠르지만 count 에 할당되는 index 가 커지면 커질 수록 메모리 낭비가 매우심함