[알고리즘] 계수 정렬 (Count Sort)

기본 개념

 

• 분포에 의한 정렬에는 계수 정렬, 기수 정렬, 버킷 정렬 등이 있으며 최악 또는 평균 실행시간이 O(n) 인 알고리즘이다.
• 계수 정렬은 입력 키가 어떤 범위(1~k) 사이의 정수 범위에 있다는 것을 알고 있을 때에만 적용할 수 있는 방법이다.
• 어떤 입력 키 x의 정렬 위치는 x보다 작은 키가 몇 개나 입력에 나타나는지를 알면 결정할 수 있다.
• 계수 정렬에서는 입력 키들이 범위 k 내의 각 값에 대하여 입력 키가 실제로 입력에 나타나는 횟수를 계산한다.

 

과정

 

 

코드

void CountSort(int a[], int n, int b[], int k)
{
	int i, j;
	int* N = new int[k];

	//N 배열 초기화 (N[] = 범위내의 각 숫자가 나타나는 횟수를 위한 배열)
	for (i = 0; i < k; i++) N[i] = 0;  //O(k)

	//각 키의 개수 저장
	for (j = 0; j < n; j++)  N[a[j]-1] += 1;  //O(n)
	//각 키의 누적 합 저장
	for (i = 1; i < k; i++) N[i] += N[i - 1];  //O(k)
	//정렬 결과를 배열 B에 저장
	//뒤에서부터 정렬하여 안정성을 보장
	for (j = n-1; j >= 0; j--) { 
		b[N[a[j]-1]-1] = a[j];
		N[a[j]-1] -= 1;
	} // O(n)
	//-> O(k)+O(n)=O(max(k,n)
}

 

실행 시간

O(n+k)