이번에는 특이한 정렬 계수 정렬Counting Sort에 대해 다룹니다.

계수 정렬

비교를 하지 않는 정렬입니다. 그래서 $O(nlogn)$을 극복해 시간복잡도가 $O(n)$입니다!

Comparison Sort
N개 원소의 배열이 있을 때, 이를 모두 정렬하는 가짓수는 N!임
따라서, Comparison Sort를 통해 생기는 트리의 말단 노드가 N! 이상의 노드 갯수를 갖기 위해서는, 2^h >= N! 를 만족하는 h를 가져야 하고, 이 식을 h > O(nlgn)을 가져야 한다. (h는 트리의 높이,,, 즉 Comparison sort의 시간 복잡도임) - Gyoogle님 블로그

방식을 전개하자면,

1. 원소 중 제일 큰 숫자정도 크기의 배열을 생성합니다. -> counting 배열
2. 배열을 순회하면서 각 counting[숫자]를 증가시킵니다.
3. counting 배열을 누적합합니다.
4. 역순으로 배열을 돌면서 해당하는 값의 인덱스에 값을 넣어줍니다
   (배열은 0-base이므로, 미리 빼줘야해요).

특징

시간 복잡도는 정확힌 $O(n+k)$로, 여기서 k는 원소 중 최대 값이에요.

속도는 빠르지만, 특수한 상황에서밖에 사용 못하고, counting 배열과 정렬 결과를 담은 배열을 따로 만들기 때문에 In-place하지 못해요. 그리고 최대 값이 크면 그만큼 불필요한 배열의 크기를 초기화하기 때문에 메모리를 많이 잡아 먹습니다.

그래도 이따금씩 이를 활용한 문제가 존재하고, 이후 기수 정렬Radix Sort에서도 활용할 수 있으니 알아두시면 좋습니다.

소스

#include <vector>
#include <limits.h>

using namespace std;

class CountingSort
{
public:
	static void sort(vector<int>& arr)
	{
		vector<int> ret(arr.size(), 0);
		vector<int> counting(getMax(arr) + 1, 0);

		for(int i = 0 ; i < arr.size(); ++i)
			counting[arr[i]]++;

		for(int i = 1; i < counting.size(); ++i)
			counting[i] += counting[i - 1];

		for(int i = arr.size() - 1; i >= 0; --i)
			ret[--counting[arr[i]]] = arr[i];
		
		arr = ret;
	}

private:
	static int getMax(const vector<int>& arr)
	{
		int ret = INT_MIN;
		for(const int& a : arr)
		{
			if(ret < a)
				ret = a;
		}
		return ret;
	}
};

참고

soobarkbar님 블로그
Gyoogle님 블로그