[알고리즘] 카운팅 정렬(Counting Sort)

1. 특징

• 원소간 비교를 수행하지 않는 정렬이다.
• 모든 원소는 양의 정수여야 함
• 시간 복잡도는 O(n+k), k는 정렬할 배열의 최대값이다.
• 공간 복잡도는 O(n+k), 정렬을 위한 배열 하나, 카운팅을 위한 배열 하나가 필요하다.

2. 과정

1. 입력 자료 input을 탐색하여 최대값 k를 구한다.
2. k + 1 사이즈의 배열 counts를 생성한다.
3. input을 순회하며, 등장하는 수의 빈도를 기록한다.. (input의 원소가 3이라면, counts[3]에 +1)
   1. 0이 1번, 2가 5번 등장하는 배열이라면, counts배열은 [1, 0, 0, 5]가 될 것
4. input을 순회하며 누적합을 구한다.
   1. 오름차순 정렬의 경우, 이전 값 (i-1)을 i에 더한다.
   2. 내림차순 정렬의 경우, input의 뒤쪽부터 시작해서, i-1에 i를 더한다.
   3. 누적합은, 정렬될 배열에서 차지할 위치를 의미함
5. output 배열을 생성한다.
6. input 배열을 뒤부터 순회하며 다음 과정을 처리한다.
   1. 현재 값이 w라면, counts[w]에 접근한다.
   2. counts[w] - 1 이 정렬된 w의 위치이다.
   3. output[counts[w] - 1]을 수행하고 나서, counts[w]를 -1 해준다.
   4. 뒤부터 순회하는 이유는, Stable하게 정렬하기 위해서이다.

3. 코드

void CountingSort(const vector<int>& input)
{
    int k = *max_element(input.begin(), input.end());

    vector<int> countArr(k + 1, 0);
    for (int i = 0; i < input.size(); ++i)
    {
        ++countArr[input[i]];
    }

    for (int i = 1; i < countArr.size(); ++i)
    {
        countArr[i] += countArr[i - 1];
    }

	// 내림차순
 //	for (int i = countArr.size() - 1; i > 0; --i)
 //	{
 //		countArr[i - 1] += countArr[i];
 //	}

    vector<int> ans(input.size());

    for (int i = 0; i < input.size(); ++i)
    {
        ans[countArr[input[i]] - 1] = input[i];
        --countArr[input[i]];
    }
}

4. 성능

• O(n + k)이므로, 등장하는 값의 범위가 작을 경우 상수시간에 가깝게 동작할 수 있다.
• 등장하는 값의 범위가 넓은 경우 공간복잡도와 시간복잡도 선에서 모두 손해
• 0~10000사이의 값을 가진 10000개의 배열에 대해 시간 측정해보니 버블소트나 선택정렬보다 매우 효율적이었다.