계수 정렬(Counting Sort)

계수 정렬이란?

비교 기반 정렬 알고리즘이 아닌 정렬 방식으로, 정수나 정수로 변환 가능한 값을 갖는 데이터에 효율적으로 사용할 수 있는 정렬 알고리즘이다. 계수 정렬의 기본 원리는 각 요소가 몇 번 등장하는지 세어서 정렬하는 방식이다.(그래서 계수이다.) 이 방법은 데이터의 크기가 제한된 경우에 특히 유용하며, 매우 빠른 실행 속도를 자랑한다.

 

다음은 계수 정렬을 하는 방법이다.

1. 원본 배열에서 최댓값과 최솟값을 찾는다. (계수 배열의 크기를 결정하기 위해서)
2. 최솟값에서 최댓값까지 각 정수가 원본 배열에 나타난 빈도만큼 기록을 하는 배열을 만든다. (계수 배열)
3. 원본 배열을 순회하면서 각 정수가 몇번 나왔는지 누적해서 기록한다. (누적 계수 배열)
4. 누적 계수 배열을 사용하여 원본 배열을 정렬된 순서로 다시 작성한다. 이때, 누적 계수 배열의 각 인덱스는 해당 요소가 정렬된 결과 배열에 들어갈 위치를 알려준다.

예시를 통해서 다시 자세히 알아보자.

예를들어 다음과 같은 원본 배열이 주어졌다.

[4, 2, 2, 8, 3, 3, 1]

 

.최댓값은 8이고 최솟값은 1이다.

그렇다면 계수 배열의 크기는.. 8 - 1 + 1 (최댓값 - 최솟값 + 1) = 8 이다.

 

그렇다면 여기서 의문이 생긴다.

왜.. 계수 배열의 크기는 최댓값과 최솟값으로 정하는거지?

 

계수 정렬에서 최솟값과 최댓값을 사용하여 배열의 크기를 결정하는 것은 계수 정렬의 핵심적인 부분이다. 이는 계수 정렬이 빈도나 누적 빈도를 기록해서 정렬을 하기 때문이다. 계수 정렬은 비교 기반 정렬 방식과 달리, 입력 데이터의 특정 범위 내의 값을 직접적으로 인덱싱하여 정렬을 수행한다.

 

최솟값에서 최댓값까지 각 정수들의 빈도를 계산할 배열을 초기화 한다.

// 배정된 정수
 1  2  3  4  5  6  7  8
[0, 0, 0, 0, 0, 0, 0, 0]

 

각 정수들의 빈도를 계산해 계수 배열을 만든다.

// 원본 배열 
[4, 2, 2, 8, 3, 3, 1]

// 배정된 정수
 1  2  3  4  5  6  7  8
[1, 2, 2, 1, 0, 0, 0, 1]

// 위 배열은 각 정수 별로 빈도를 계산한 계수 배열이다.

 

계수 배열을 누적해가면서 누적 계수 배열을 만든다.

// 원본 배열 
[4, 2, 2, 8, 3, 3, 1]

// 배정된 정수
 1  2  3  4  5  6  7  8
// 계수 배열 
[1, 2, 2, 1, 0, 0, 0, 1]
// 누적 계수 배열
[1, 3, 5, 6, 6, 6, 6, 7]

 

 

이때, 잘.. 생각해보면,

누적 계수 배열의 각 값이 그 값보다 작거나 같은 수들의 총 개수를 나타낸다.

최솟값인 1의 자리에 해당하는 누적 계수 배열값은 1, 즉 지금까지 하나의 정수만이 누적되었음을 나타낸다.

그 다음, 2의 자리에 해당하는 누적 계수 배열값은 3, 즉 지금까지 3개의 정수가 누적되었음을 나타낸다.

계속해서 정수 3까지, 정수 3보다 작거나 같은 정수는 5개가 누적되었음을 나타낸다.

참고로, 정수 5, 6, 7의 경우 한번도 출현하지 않았으므로 누적 계수 배열이 증가되지 않는 것이다.

마지막 최댓값인 8의 자릿수까지 오게되면, 지금까지 출현한 정수의 총 개수가 반환될 수 밖에 없다.

 

이러한 계수 배열의 특성을 살려서, 원본 배열을 정렬해보자.

누적 계수 배열의 각 정수 값은, 원본 배열의 정수들이 결과 배열에 배치되어야 할 위치이다..

따라서, 원본 배열의 역순으로 정수를 조회하면서, 누적 계수 배열로 정렬된 결과 배열을 만들어낸다..

 

? 난 여기서 이해가 안됐다.. 더 자세하게 설명해보겠다.

 

먼저, 누적 계수 배열은 각 원소의 값이 결과 배열에서 나타나야 할 마지막 위치를 나타낸다.

그야 당연하다. 정수를 오름차순으로 정렬하여 빈도를 계산했기 때문이다.

계수 배열의 idx = 0 에 해당하는 값은 정수 1의 빈도 값이고,

idx = 1 에 해당하는 값은 정수 2의 빈도 값이기 때문이다.

 

마지막으로, 실제로 배열을 채울 때는 각 숫자를 배치한 후에 그 숫자의 누적합을 1 감소시켜, 같은 숫자가 다음에 등장할 때 그 앞 위치에 들어갈 수 있도록 한다. 

 

누적 계수 배열은 원소의 값이 결과 배열에서 나타나야할 마지막 위치라고 했다. 그에 따라서 숫자를 배치하면 다음에 같은 숫자가 나올 수도 있으니 그 전 위치에 배정될 수 있도록 마지막위치를 -1 하는 것이다.