계수 정렬 (counting sort) : 특정 숫자의 빈도를 센다.

 2가지 정렬을 배웠습니다. insert, select. 이 두 개는 키 값들을 비교를 했습니다. 2개의 값을 compare 했습니다. 제가 오늘 설명하는 counting sort, 계수 정렬은 이 둘과 크게 다른 점이 있는데요. 두 개의 키 값을 비교하지 않는다는 것입니다. 즉, 비교 기반 정렬이 아닙니다. 그러면 어떻게 구현을 할까요?

 

 

---

 arr = [3, 6, 3, 0, 4, 1]이라고 해 봅시다. 최솟값이 양수고, 최댓값 또한 적당히 작은 수라고 해 봅시다. co[x]를, 배열에서 x가 나타난 빈도수라고 정의합시다. 그러면, arr을 순회하면서, 어떠한 값 v가 나오면 co[v]의 값을 하나씩 증가시키면 될 거에요. 먼저 co 배열은 아래와 같이 초기화가 되어 있습니다.

 

 

 1번째 원소를 봅니다. 3입니다. 따라서 co[3]의 값을 하나 증가시킵니다.

 

 

 2번째 원소의 값은 6입니다. 따라서, co[6]의 값을 하나 증가시킵니다.

 

 

 3번째 원소는 3입니다. co[3]의 값을 하나 증가시킵니다. 3이 한 번 더 나왔기 때문에, 출현 횟수는 2가 됩니다.

 

 

 다음에는 0이 나옵니다. co[0]의 값을 하나 증가시킵니다.

 

 

 그 다음에 4가 나왔습니다. 그러면, co[4]의 값을 하나 증가시킵니다.

 

 

 그리고 1이 나왔습니다. 그러면 co[1]의 값을 하나 올립니다.

 

 

 배열을 다 돌았더니, co 배열을 하나 채웠습니다. 0과 1이 1번, 3이 2번, 4가 1번, 6이 1번 나왔다는 의미입니다. 이것을 가지고 어떻게 정렬을 할 수 있을까요?

 

 

---

 0부터 6까지 돌아봅시다. co[x]만큼 x를 출력해 봅시다. 먼저 co[0]의 값은 1입니다.

 

 

 그렇기 때문에 0은 1번 출력합니다. 그 다음에 co[1]을 봅시다. 1은 1번 나왔습니다.

 

 

 그러므로 1도 1번 출력해 줍니다. 2는 몇 번 나왔나요? 0번 나왔으니까 0번 출력합니다.

 

 

 3은 어떤가요? 2번 나왔습니다. 따라서 3은 2번 출력해주면 되겠습니다. 4는 1번 나왔네요.

 

 

 그러므로 1번만 출력합니다. 5는 0번 나왔고, 6이 1번 나왔으니까, 6은 1번만 print 해 주면 되겠네요.

 

 

 sorting이 끝났습니다. 즉, 어떤 수가 몇 번 나왔느냐를 카운트 하는 배열만 있으면, 그 array를 순회하면서 소팅을 할 수 있는 셈입니다.

 

 

---

 그런데 배열 안에 있는 수가 999억, 999억 1, 999억 2일 때에는 어떻게 처리해야 하나요? 혹은, -100억, -99억 9999 이럴 때에는 어떻게 처리해야 할까요? 그냥 co[999억]++을 하자니 뭔가 힘들어 보입니다. 혹은 co[-100억]++ 도 마찬가지일 거고요.

 

 

 먼저 arr에서 가장 작은 수를 찾습니다. 이를 기준 수, standard라고 합시다. 위 그림에서는 -30억 5임을 알 수 있어요.

 

 

 즉, standard는 -30억 5가 됩니다. arr의 각 요소들에다가 standard를 빼 봅시다.

 

 

 그러면 이런 식으로 나올 겁니다. 이제 이것을 co 배열에 채워 보면 다음과 같이 나옵니다.

 

 

 실제로 이 때 co[x]의 의미는, x+standard가 co[x]개 있다는 의미입니다. 즉, co[0]이 1이라는 것은 0 + (-30억 5)가 1개가 있다는 의미이고, co[5]가 1이라는 것은 5 + (-30억 5)가 1개 있다는 의미입니다. 즉, x에 대해서 x+standard를 co[x]번 출력하면 됩니다.

 

 이것을 코드로 봅시다.

 

 

---

 배열의 크기가 최대 1000만이고, 들어올 수 있는 수는 [-10000, 10000] 구간에 속하는 정수라고 해 봅시다.

 

 

 먼저 arr에 있는 수들 중 제일 작은 값인 mmn을 구합니다. 이를 standard라고 했어요. 이 값을 co 배열에서의 0에 대응시킵니다. mmn + 1은 1에 대응시키고요. 그럴려면 arr[i]는 co 배열에서 arr[i] - mmn에 대응될 거에요. 16번째 줄이 그것을 잘 보여줍니다.

 

 

 다음에 co[i]를 돌면서 출력을 해야 하는데요. 수 i는 co에서 i - mmn에 대응되었어요. 그러면 co에서 i - mmn은 실제 i와 대응이 될 거에요. (i - mmn) + mmn = i 에요. 역변환이라고 생각하면 조금 더 편할까요? 그렇기 때문에, i + mmn을 co[i]번 출력해 주면 됩니다.

 

 실제로 계수 정렬, counting sort는 복잡도가 O(|max_value - min_value| + n)이 되는데요. 최댓값과 최솟값의 차이가 작다면 상당히 빠르다는 것을 알 수 있습니다. 최댓값과 최솟값의 차이가 상당히 크다면, 다른 방법을 써야 하는데요. 이것은 다음에 배워보도록 하겠습니다.