[알고리즘] 정렬(4) - 계수 정렬(Counting Sort)

 원리 

1. 집합의 최댓값을 구해서 최대값만큼의 메모리를 차지하는 카운팅 배열을 만든다.

2. 각원소의 개수를 카운팅시킨다

3. 카운팅 배열의 누적합을 구한다.

4. 카운팅 배열을 통해 순서대로 수를 나열한다.

 

[ 15, 13, 10, 7, 5, 5, 1, 0, 7 ]

 

카운팅 배열에는 다음과 같이 구성될 수 있습니다.

Index	0	1	5	7	10	13	15
count	1	1	2	2	1	1	1

 

다음을 누적합의 표입니다.

Index	0	1	5	7	10	13	15
count	1	2	4	6	7	8	9

 

이때, 누적합을 구하는 이유는 어느 인덱스에 원본 원소가 들어갈지 순서를 강제하기 위해서 입니다.

정렬된 원소들이 들어갈 배열의 인덱스를 카운팅배열의 데이터 - 1로 설정 해줌으로서 정렬 해줄 수 있습니다.

 

예를들어, 연속된 수를 카운팅 정렬할때는 그저 누적합의 과정이 필요없이 나열하면 되지만, 만약 1,2,3,10000 이라는 수열 을 정렬한다고 한다면 (이미 정렬되어 있지만) 카운팅 배열을 10000까지 순회해야한다는 점 때문에 누적합 과정이 필요합니다.

 

그만큼 카운팅 정렬은 원소의 최댓값만큼의 용량을 가진 배열이 필요하고, 정수만을 정렬 할 수 있다는 단점이 있습니다.

 

 구현 

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 20;

vector<int> CountingSort(const vector<int>& data)
{
	int sz = data.size();         	 // 원본 배열의 사이즈
	int mx = -0x07fffffff;
	for (int d : data)
		mx = max(d, mx);         	 // 배열의 최댓값

	vector<int> cnt(mx + 1, 0);      // 카운팅 배열

	/* 원소의 수만큼 카운트 */
	for (int i = 0; i < sz; ++i)
		cnt[data[i]]++;

	/* 누적합 구하기 */
	for (int i = 1; i < mx + 1; ++i)
		cnt[i] = cnt[i - 1] + cnt[i];

	vector<int> answer(sz);      	  // 결과를 저장할 배열

	/* 정렬 하기 */
	for (int i = sz - 1; i >= 0; --i)
		answer[--cnt[data[i]]] = data[i];

	return answer;
}

int main()
{
	ios::sync_with_stdio(0), cin.tie(0);
	clock_t s, e;
	vector<int> arr(MAX_N);
	srand((unsigned int)time(NULL));


	for (int t = 0; t < 5; ++t)
	{
		for (int i = 0; i < MAX_N; ++i)
			arr[i] = rand() % MAX_N;

		s = clock();

		arr = CountingSort(arr);

		e = clock();

		cout << (double)(e - s) / CLOCKS_PER_SEC << '\n';
	}

}

 

 

 

 시간복잡도 

카운팅 정렬은 최대값 구하기, 누적합 구하기, 정렬하기 총 3번의 반복을 하기때문에 시간복잡도는 O(n)로 빠릅니다. 적절하게 사용한다면 효율이 굉장히 좋을것입니다.

 

 정리 

이름	BEST	AVG	WORST	RUN TIME(정수 60,000)
버블 정렬	n^2	n^2	n^2	확인
선택 정렬	n^2	n^2	n^2	확인
삽입 정렬	n	n^2	n^2	확인
계수 정렬	n	n	n	사진 참고

계수 정렬 런타임 (정수 60,000개)

당연히 약 0ms의 런타임이 측정되었습니다.

 

실행 환경 :

- windows 10 WSL2 - ubuntu 18.04

- gcc 7.4.0

- cpu : i3

 

 참조 

-