이전 글(Heap Sort)에서 정렬 알고리즘의 중요한 공통점을 하나 짚었습니다. Heap Sort, Quick Sort, Merge Sort는 모두 구조와 방식은 달라도 결국 값을 서로 비교(compare)하며 순서를 결정한다는 점입니다. 이 때문에 비교 기반 정렬은 이론적으로 O(N log N)보다 더 빨라질 수 없으며, 알고리즘에 따라서는 최악의 경우 그보다 더 느려질 수도 있습니다.
그렇다면 자연스럽게 이런 질문이 생깁니다. “O(N log N)보다 빠른 정렬은 정말 없는가?”, 이 질문에 대한 대답이 바로 이 글에서 다룰 Counting Sort입니다.
해답은 의외로 단순합니다. 비교를 하지 않으면 됩니다. Counting Sort는 원소들끼리 크고 작음을 비교하지 않습니다. 대신 값의 범위라는 정보를 활용해 정렬을 수행합니다. 이 때문에 특정 조건에서는 O(N log N)을 넘어서는 선형 시간 정렬(O(N + K))이 가능해집니다. 여기서 K는 값의 범위를 의미합니다.
1. Counting Sort의 핵심 아이디어
Counting Sort의 아이디어는 매우 직관적입니다.
- 값을 서로 비교하지 않는다
- 값 자체를 배열의 인덱스로 사용한다
- 각 값이 몇 번 등장했는지를 센다
즉, “이 값이 저 값보다 큰가?”를 묻지 않습니다. 대신 “이 값이 몇 번 나왔는가?”만을 기록합니다.
이 방식이 가능한 이유는, 정렬 대상이 연속적인 정수 범위 안에 있다고 가정하기 때문입니다. 따라서 Counting Sort가 사용되기 위한 조건은 명확합니다.
- 데이터가 정수여야 한다
- 값의 최소값과 최대값의 차이(범위)가 크지 않아야 한다
이 조건이 맞을 때, Counting Sort는 비교 기반 정렬이 절대 따라올 수 없는 속도를 보여줍니다.
2. 예제로 이해하는 Counting Sort
다음과 같은 정수 배열이 있다고 가정해 보겠습니다.
[9, 7, 10, 7, 13, 9, 11]이 배열의 최소값은 7, 최대값은 13입니다.
Counting Sort에서는 실제 값의 크기가 아니라, 값의 범위(최대값 - 최소값 + 1)만큼의 count 배열을 생성합니다. 따라서 이 예제에서 필요한 count 배열의 크기는 다음과 같습니다.
13 - 7 + 1 = 7즉, 크기 7의 count 배열을 생성합니다. 각 값은 value - min 방식으로 0부터 매핑됩니다.
초기 상태의 count 배열은 다음과 같습니다.
index: 0 1 2 3 4 5 6
value: 7 8 9 10 11 12 13
count: 0 0 0 0 0 0 0
이제 원본 배열을 한 번 순회하며 등장 횟수를 셉니다.
값 9 → count[9 - 7]++ → count[2]++
값 7 → count[7 - 7]++ → count[0]++
값 10 → count[10 - 7]++ → count[3]++
값 7 → count[7 - 7]++ → count[0]++
값 13 → count[13 - 7]++ → count[6]++
값 9 → count[9 - 7]++ → count[2]++
값 11 → count[11 - 7]++ → count[4]++
집계가 끝난 count 배열은 다음과 같습니다.
index: 0 1 2 3 4 5 6
value: 7 8 9 10 11 12 13
count: 2 0 2 1 1 0 1
이 배열이 의미하는 바는 명확합니다.
- 7은 2번 등장
- 9는 2번 등장
- 10은 1번 등장
- 11은 1번 등장
- 13은 1번 등장
이제 count 배열을 앞에서부터 순회하며, 각 인덱스를 등장 횟수만큼 출력하면 정렬이 완성됩니다.
결과: [7, 7, 9, 9, 10, 11, 13]
이 방식은 누적합을 사용하지 않는 기본적인 Counting Sort입니다. 값의 정렬 결과만 필요하다면 이 방식으로 충분합니다. 반면, 누적합(count prefix sum)을 사용하는 방식은 각 값이 최종 배열에서 차지할 정확한 위치를 계산하는 데 사용되며, 이 차이는 뒤에서 설명할 안정 정렬(Stable Sort)과 직접적으로 연결됩니다.
count 배열만을 이용해 값을 출력하는 방식은 정렬 대상이 ‘값 그 자체’일 때만 의미가 있습니다. 값과 함께 이동해야 할 부가 정보가 있는 경우에는, 이 방식으로는 정렬을 수행할 수 없습니다.
이러한 경우에는 누적합을 이용해 각 원소가 들어갈 정확한 위치를 계산한 뒤, 원본 배열의 원소를 결과 배열로 이동시키는 방식이 필요합니다.
📌 누적합(Prefix Sum)과 실제 정렬 과정
누적합(Prefix Sum)이란, 각 값이 자기 자신까지 총 몇 개의 원소가 존재하는지를 미리 계산해 두는 방법입니다.
먼저, Counting Sort에서 얻은 count 배열은 각 값이 몇 번 등장했는지만을 담고 있습니다.
원본 배열: [9, 7, 10, 7, 13, 9, 11]
index: 0 1 2 3 4 5 6
value: 7 8 9 10 11 12 13
count: 2 0 2 1 1 0 1
이 배열을 누적합으로 변환한다는 것은, 왼쪽부터 차례대로 값을 더해 가며 현재 인덱스까지의 전체 등장 횟수를 계산하는 것을 의미합니다.
실제 계산 과정은 다음과 같습니다.
prefix[0] = 2
prefix[1] = 2 + 0 = 2
prefix[2] = 2 + 2 = 4
prefix[3] = 4 + 1 = 5
prefix[4] = 5 + 1 = 6
prefix[5] = 6 + 0 = 6
prefix[6] = 6 + 1 = 7
따라서 누적합 배열은 다음과 같이 변환됩니다.
index: 0 1 2 3 4 5 6
value: 7 8 9 10 11 12 13
prefix sum: 2 2 4 5 6 6 7
여기서 중요한 점은, 이 누적합 배열이 더 이상 단순한 “개수”가 아니라 정렬된 결과 배열에서의 자리 정보라는 것입니다. 누적합을 가장 쉽게 이해하는 방법은 “정렬된 결과 배열의 자리를 미리 예약해 둔 표”라고 생각하는 것입니다.
- 값 7은 총 2번 등장하므로, 정렬된 결과 배열의 가장 앞쪽인 index 0 ~ 1을 차지하게 됩니다.
- 값 9는 누적합이 4이므로, 결과 배열의 앞에서부터 총 4칸(index 0 ~ 3)을 차지해야 합니다. 이 중 index 0 ~ 1은 이미 값 7이 사용하고 있으므로, 그 다음 구간인 index 2 ~ 3에 배치됩니다.
- 값 13은 누적합이 7로, 전체 원소 수와 같기 때문에 정렬된 결과 배열의 마지막 위치인 index 6에 배치됩니다.
즉, 누적합 값은 “이 값들이 어디까지 배치될 수 있는지”를 알려주는 자리의 끝 위치입니다.
정렬 과정에서 어떤 값이 한 번 배치되면, 해당 값의 누적합 값을 1 감소시킵니다. 이는 “이 값이 사용할 수 있는 마지막 자리를 하나 소비했다”는 의미이며, 다음에 같은 값이 나오면 그보다 한 칸 앞의 자리에 배치되도록 하기 위함입니다.
이제 이 누적합 정보가 실제 정렬 과정에서 어떻게 사용되는지를 살펴보겠습니다.
원본 배열: [9, 7, 10, 7, 13, 9, 11]
index: 0 1 2 3 4 5 6
value: 7 8 9 10 11 12 13
count: 2 0 2 1 1 0 1
prefix sum: 2 2 4 5 6 6 7
결과 배열의 크기는 7이며, 처음에는 비어 있다고 가정합니다.
result: [_, _, _, _, _, _, _]
이제 원본 배열을 뒤에서부터 하나씩 꺼내며 정렬을 진행합니다.
① 마지막 값은 11입니다.
누적합 값은 6이므로, 들어갈 위치는 6 - 1 = 5입니다.
result: [_, _, _, _, _, 11, _]
② 다음 값은 9입니다.
누적합 값은 4 → 위치는 4 - 1 = 3입니다.
result: [_, _, _, 9, _, 11, _]- 배치 후에는 해당 값의 누적합 값을 1 줄여, 다음 9는 그보다 앞자리에 들어가게 됩니다.
③ 다음 값은 13입니다.
누적합 값은 7 → 위치는 7 - 1 = 6입니다.
result: [_, _, _, 9, _, 11, 13]
④ 다음 값은 7입니다.
누적합 값은 2 → 위치는 2 - 1 = 1입니다.
result: [_, 7, _, 9, _, 11, 13]
⑤ 다음 값은 10입니다.
누적합 값은 5 → 위치는 5 - 1 = 4입니다.
result: [_, 7, _, 9, 10, 11, 13]
⑥ 다음 값은 다시 7입니다.
이전에 하나를 사용했으므로, 다음 자리인 index 0에 배치됩니다.
result: [7, 7, _, 9, 10, 11, 13]
⑦ 마지막 값은 9입니다.
남은 자리는 index 2입니다.
result: [7, 7, 9, 9, 10, 11, 13]
이렇게 모든 원소가 정렬된 결과 배열에 배치됩니다.
중요한 점은, 같은 값을 가진 원소를 뒤에서부터 처리했기 때문에 먼저 등장했던 원소가 결과 배열에서도 앞쪽에 그대로 남아 있다는 것입니다. 그 결과, 같은 값들의 상대적인 순서가 깨지지 않게 되며, 누적합을 사용하는 Counting Sort는 안정 정렬(Stable Sort)이 됩니다.
※ 동작을 시각적으로 확인해보기
아래 링크는 Counting Sort의 전체 동작 과정을 단계별로 시각화해 줍니다. 값을 비교하지 않고, count 배열 → 누적합 → 결과 배열 배치로 이어지는 흐름을 직접 눈으로 확인할 수 있습니다.
특히
- 각 값이 몇 번 등장하는지
- 누적합이 “자리의 끝 위치”로 어떻게 바뀌는지
- 왜 원본 배열을 뒤에서부터 순회해야 안정 정렬이 되는지
를 함께 살펴보면, 글에서 설명한 내용이 훨씬 직관적으로 이해될 것입니다.
https://www.cs.usfca.edu/~galles/visualization/CountingSort.html
3. 시간 복잡도는 왜 O(N + K)인가
Counting Sort의 시간 복잡도는 O(N + K)입니다.
- N: 정렬할 데이터의 개수
- K: 값의 범위 (max - min + 1)
이유는 단순합니다.
- 원본 배열을 한 번 순회하며 count → O(N)
- count 배열을 순회하며 결과 생성 → O(K)
비교 연산이 없기 때문에, 데이터 수가 많아져도 log 연산이 붙지 않습니다. 조건만 맞는다면 진짜 의미의 선형 시간 정렬이 됩니다.
하지만 중요한 단점도 분명합니다. K가 커지면 오히려 느려집니다. 예를 들어 데이터는 100개인데 값의 범위가 0~1,000,000이라면, count 배열을 만드는 것 자체가 큰 낭비가 됩니다. 이 경우에는 Heap Sort나 Quick Sort가 훨씬 현실적인 선택입니다.
4. Counting Sort와 안정 정렬(Stable)
Counting Sort는 흔히 “안정 정렬”로 소개되지만, 정확히 말하면 구현 방식에 따라 안정성이 달라집니다. 앞에서 살펴본 것처럼, count 배열만을 이용해 값을 출력하는 방식은 정렬 결과는 만들 수 있지만, 같은 값을 가진 원소들의 상대적인 순서는 보장할 수 없습니다. 이 방식은 값 자체만 정렬할 때에만 의미가 있으며, 부가 정보(payload)를 함께 이동시켜야 하는 경우에는 안정 정렬이 될 수 없습니다.
반면, count 배열을 누적합으로 변환하여 각 값이 들어갈 정확한 위치를 계산한 뒤, 원본 배열을 뒤에서부터 순회하며 결과 배열을 채우는 방식은 같은 값의 상대적인 순서를 유지할 수 있습니다. 이 방식이 바로 안정 정렬을 보장하는 누적합 기반 Counting Sort입니다. 이 누적합 기반 Counting Sort는 Counting Sort의 확장일 뿐만 아니라, 다음 글에서 다룰 Radix Sort를 구성하는 핵심 요소이기도 합니다.
지금 단계에서는, Counting Sort가 단독으로도 사용될 수 있지만, 보다 복잡한 정렬 알고리즘의 기반으로도 활용된다는 점만 기억해 두시면 충분합니다.
5. C# Counting Sort 구현
아래는 범위 계산을 포함한, 읽기 쉬운 C# 기반 Counting Sort 구현입니다.
using System;
namespace Daebak.Common.Algorithms.Sorting
{
/// <summary>
/// Counting Sort (카운팅 정렬)
/// - 비교 기반 정렬이 아닌 "값의 범위"를 이용하는 정렬
/// - 시간 복잡도: O(N + K)
/// - N: 데이터 개수
/// - K: 값의 범위 (max - min + 1)
/// - 추가 메모리: O(K) (count 배열, Stable 구현 시 output 배열 O(N) 추가)
/// - 조건:
/// - 정수 데이터에 적합
/// - 값의 범위(K)가 너무 크면 메모리/시간 면에서 비효율적일 수 있음
///
/// 안정성(Stable):
/// - "count만 보고 값을 출력"하는 단순 구현은 Stable을 보장하지 않음(값만 정렬할 때 의미)
/// - "누적합 + 뒤에서부터 배치" 구현은 Stable을 보장 (Radix Sort의 기반)
/// </summary>
public static class CountingSort
{
/// <summary>
/// 외부에서 호출되는 진입점
/// - 전체 배열을 대상으로 Counting Sort 수행 (오름차순)
/// - 기본 Sort()는 "값만 정렬" 버전으로 제공 (Stable X)
/// - Stable이 필요하면 SortStable을 사용
/// </summary>
public static void Sort(int[] array)
{
if (array == null || array.Length <= 1)
{
return;
}
// 1) min/max 계산 (범위 산출)
GetMinMax(array, out int minValue, out int maxValue);
// 2) 값만 정렬 결과가 필요할 때 (Stable 보장 X, payload 이동 불가)
SortValuesOnly(array, minValue, maxValue);
// 3) Stable이 필요할 때 (누적합 기반, Radix Sort에서 사용)
//SortStable(array, minValue, maxValue);
}
/// <summary>
/// 배열에서 min/max를 구한다.
/// - Counting Sort의 핵심인 "범위(K)"를 계산하기 위함
/// </summary>
private static void GetMinMax(int[] array, out int minValue, out int maxValue)
{
minValue = array[0];
maxValue = array[0];
for (int i = 1; i < array.Length; i++)
{
int v = array[i];
if (v < minValue)
{
minValue = v;
}
if (v > maxValue)
{
maxValue = v;
}
}
}
/// <summary>
/// (1) 값만 정렬 결과가 필요할 때 사용하는 단순 Counting Sort
/// - count 배열을 만든 뒤, 작은 값부터 count만큼 "값을 써 넣는 방식"
/// - 주의: Stable을 보장하지 않음
/// - 주의: payload(부가 데이터)를 함께 이동시키는 정렬에는 사용할 수 없음
/// </summary>
private static void SortValuesOnly(int[] array, int minValue, int maxValue)
{
int range = maxValue - minValue + 1;
// range가 지나치게 크면 O(K) 메모리/시간 비용이 커진다.
// (예: 값이 듬성듬성 크고 범위만 큰 경우)
int[] count = new int[range];
// 1) 등장 횟수 집계
for (int i = 0; i < array.Length; i++)
{
int index = array[i] - minValue;
count[index]++;
}
// 2) count를 앞에서부터 순회하며 값을 채워 넣는다.
int write = 0;
for (int i = 0; i < range; i++)
{
int value = i + minValue;
int c = count[i];
while (c > 0)
{
array[write] = value;
write++;
c--;
}
}
}
/// <summary>
/// (2) Stable Counting Sort (누적합 기반)
/// - count(등장 횟수) → prefix sum(누적합)으로 변환
/// - 원본 배열을 뒤에서부터 순회하며 output에 배치
/// - Stable을 보장 (동일 값의 상대 순서 유지)
/// </summary>
private static void SortStable(int[] array, int minValue, int maxValue)
{
int range = maxValue - minValue + 1;
// range가 지나치게 크면 O(K) 메모리/시간 비용이 커진다.
int[] count = new int[range];
// 1) 등장 횟수 집계
for (int i = 0; i < array.Length; i++)
{
int index = array[i] - minValue;
count[index]++;
}
// 2) 누적합(prefix sum)으로 변환
// count[i]가 "해당 값이 결과 배열에서 차지할 마지막 위치(끝+1)" 의미로 바뀐다.
for (int i = 1; i < range; i++)
{
count[i] += count[i - 1];
}
// 3) 결과 배열에 Stable하게 배치
// - 뒤에서부터 순회해야 같은 값의 상대 순서가 유지된다.
int[] output = new int[array.Length];
for (int i = array.Length - 1; i >= 0; i--)
{
int value = array[i];
int index = value - minValue;
// count[index]는 "끝 위치(1-based)" 개념이므로, 실제 인덱스는 -1
int pos = count[index] - 1;
output[pos] = value;
// 해당 값의 다음 배치 위치를 한 칸 앞으로 이동
count[index]--;
}
// 4) 결과를 원본 배열로 복사
for (int i = 0; i < array.Length; i++)
{
array[i] = output[i];
}
}
}
}제약 사항은 명확합니다.
- 정수 배열 전용
- 값의 범위가 지나치게 크면 비효율적
6. Unity 환경 테스트
Unity에서 간단히 동작을 확인해 보겠습니다.
using UnityEngine;
using Daebak.Common.Algorithms.Sorting;
public class Test_CountingSort : MonoBehaviour
{
private void Start()
{
int[] data = { 9, 7, 10, 7, 13, 9, 11 };
Debug.Log("Before Sort : " + string.Join(", ", data));
CountingSort.Sort(data);
Debug.Log("After Sort : " + string.Join(", ", data));
}
}실행 결과를 통해, 비교 없이도 정렬이 완성된다는 점을 확인할 수 있습니다.
출력 결과
Before Sort : 9, 7, 10, 7, 13, 9, 11
After Sort : 7, 7, 9, 9, 10, 11, 13
7. 마무리
Counting Sort는 분명 강력합니다. 특히 정렬 대상이 정수이고, 값의 범위가 제한적인 경우에는 비교 기반 정렬보다 훨씬 효율적인 선택이 될 수 있습니다.
- 비교 연산이 없다
- 조건이 맞으면 O(N + K)
- 구현이 단순하다
하지만 동시에 명확한 한계도 있습니다.
- 값의 범위(K)에 메모리를 직접 소비한다
- 모든 데이터에 사용할 수 없다
- 만능 정렬이 아니다
그럼에도 Counting Sort는 여기서 끝이 아닙니다. 이 정렬은 다음 단계로 나아가기 위한 중요한 발판입니다.
※ 다음 글에서는 Counting Sort의 “안정 정렬 성질”을 활용해, 더 큰 수와 자릿수를 다루는 Radix Sort를 살펴보겠습니다. 왜 Counting Sort를 먼저 이해해야 했는지, 그 이유가 자연스럽게 이어질 것입니다.
'자료 구조' 카테고리의 다른 글
| Unity 개발자를 위한 C# Radix Sort(LSD) 구현 (0) | 2026.01.21 |
|---|---|
| Unity 개발자를 위한 C# Heap Sort(힙 정렬) 구현 (0) | 2026.01.19 |
| Unity 개발자를 위한 C# Quick Sort(퀵 정렬) 구현 (0) | 2026.01.18 |
| 대박 게임 개발 연구소(Daebak Game Dev Lab) 소개 (0) | 2026.01.15 |
| Unity 개발자를 위한 C# Merge Sort(병합 정렬) 구현 (0) | 2026.01.15 |
