계수 정렬(Counting Sort)

계수 정렬은 크기를 기준으로 개수를 세는 것이며, 범위조건이 있는 경우에 한해서 사용된다.

 

5이하의 자연수 데이터들이 있다고 가정할 때, 계수 정렬은 배열 첫번째 요소부터 시작하여 해당 값이 등장할 경우

 

개수를 하나씩 증가시킨다.

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 0개, 0개, 0개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 0개, 1개, 0개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 1개, 0개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 1개, 1개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 1개, 2개, 1개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 2개, 2개, 1개, 0개

 

1, 3, 2, 4, 3, 2, 5 --> 1개, 2개, 2개, 1개, 1개

 

[예제]

 

#include <stdio.h>

int main() {
	int temp;
	int count[5];
	int array[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[array[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);
			}
		}
	}
}

 

5이하의 자연수 데이터 30개가 저장되어 있는 배열에서 계수 정렬을 수행하기 위해 우선적으로 각 1~5까지 각 자연수의

 

개수를 나타내는 배열 count[] 를 선언한다. count 배열의 원소를 모두 0으로 초기화를 시켜준 뒤, 반복문을 통해

 

30개의 자연수가 들어있는 배열 array를 탐색하면서 count배열의 각 자리에 1씩 증가하도록 한다. 

 

배열은 0부터 시작하기 때문에 count[array[i] - 1] 으로 작성할 수 있다. 반복문이 끝나고 출력할 때는

 

카운트한 개수만큼 각 자연수를 출력한다.

 

[결과]

계수정렬(Counting Sort) 결과

 

[계수 정렬의 시간 복잡도]

계수 정렬의 시간 복잡도는 O(N) 이다.

 

모든 데이터의 크기가 1~5까지 한정되어 있고, 반복문 또한 1~5까지만 반복한다는 점에서 O(N)이라고 할 수 있다.

 

---

출처

https://blog.naver.com/ndb796/221228361368

11. 계수 정렬(Counting Sort)