9. 계수 정렬 (Counting Sort) — O(n+k), 비교 불필요

핵심 인사이트 (3줄 요약)

1. 본질: 계수 정렬은 요소 간 비교 없이 각 값의 등장 횟수를 세어 정렬하는 비교 기반 하한 O(n log n)을 돌파하는 알고리즘이다.
2. 가치: 키 범위 k가 작은 정수 데이터(성적, 나이, 코드값 등)에서 O(n+k) 선형 시간을 달성하며 안정 정렬(Stable Sort) 성질을 보장한다.
3. 판단 포인트: k >> n 인 경우(예: 32비트 정수 전체 범위) 메모리와 시간이 폭발적으로 증가하므로, 기수 정렬(Radix Sort)로 전환하거나 적용 대상을 제한해야 한다.

Ⅰ. 개요 및 필요성

비교 기반 정렬(Comparison-Based Sort)의 이론적 하한은 **Ω(n log n)**이다. 이 한계를 돌파하려면 비교 연산 외의 추가 정보(값의 범위)를 활용해야 한다. **계수 정렬 (Counting Sort)**은 입력 데이터가 0부터 k까지의 정수라는 조건 하에, 각 값이 몇 번 등장하는지 세는 방식으로 O(n+k) 시간 복잡도를 달성한다.

적용 전제 조건

📢 섹션 요약 비유: 계수 정렬은 학급 시험 성적 집계와 같다. 100점 만점 시험이라면 0~100점 칸이 있는 집계표에 표시만 하면 되고, 누가 누구보다 높은지 일일이 비교할 필요가 없다.

Ⅱ. 아키텍처 및 핵심 원리

알고리즘 3단계

1. Count 단계: 입력 배열을 순회하며 count[v]++ (값 v의 등장 횟수 기록)
2. Prefix Sum 단계: count[i] += count[i-1] (누적합 → 각 값의 마지막 위치)
3. Place 단계: 입력 배열을 역순으로 순회하며 output[count[v]-1] = v, count[v]-- (안정 정렬 보장)

ASCII 다이어그램 — 계수 정렬 동작 과정

입력: [3, 1, 4, 1, 5, 2, 3, 2]  (k=5)

── 1단계: Count ──────────────────────────────────
인덱스:  0   1   2   3   4   5
count: [ 0,  2,  2,  2,  1,  1 ]
              ↑   ↑   ↑   ↑   ↑
              1이  2가  3이  4가  5가
              2번  2번  2번  1번  1번

── 2단계: Prefix Sum ─────────────────────────────
인덱스:  0   1   2   3   4   5
count: [ 0,  2,  4,  6,  7,  8 ]
        누적합: count[i]번째 위치까지가 값 i의 끝

── 3단계: Place (역순 순회로 안정성 보장) ──────────
입력 역순: [2, 3, 2, 5, 1, 4, 1, 3]
 v=2: output[count[2]-1] = output[3] = 2, count[2]=3
 v=3: output[count[3]-1] = output[5] = 3, count[3]=5
 ...

출력: [1, 1, 2, 2, 3, 3, 4, 5] ✅

시간/공간 복잡도

📢 섹션 요약 비유: 세 단계는 투표 → 집계 → 결과 공고와 같다. 투표함(count)에 표를 넣고(1단계), 누적 집계(2단계)하면, 각 후보의 결과 위치가 확정되어 발표(3단계)만 하면 된다.

Ⅲ. 비교 및 연결

비교 기반 vs 비비교 기반 정렬

유사 알고리즘 비교

📢 섹션 요약 비유: 계수 정렬, 기수 정렬, 버킷 정렬은 모두 "특화된 도구"다. 계수 정렬은 소규모 범위 정수 전용 렌치, 기수 정렬은 자릿수 전용 드라이버, 버킷 정렬은 균등 분포 전용 스패너다.

Ⅳ. 실무 적용 및 기술사 판단

적합한 사용 사례

시나리오 1 — 학생 성적 정렬: 0~100점, n=10만 명
→ k=101, n=100,000 → O(100,101) ≈ O(n) ✅
→ 병합 정렬 O(n log n) ≈ 1,700,000 연산 대비 약 17배 빠름

시나리오 2 — 기수 정렬의 서브루틴: 기수 정렬은 각 자릿수(digit)마다 계수 정렬을 적용하므로, 계수 정렬의 안정성이 전체 알고리즘 정확성의 핵심

시나리오 3 — DNA 염기서열 정렬: A/T/G/C 4종류(k=4)로 O(n+4) = O(n) 달성 가능

주의사항 (기술사 판단 기준)

┌──────────────────────────────────────────────────────┐
│  계수 정렬 적용 가능 여부 판단 흐름도                  │
│                                                      │
│  입력이 정수인가? ──No──→ 사용 불가 (비교 정렬 사용)  │
│        │ Yes                                         │
│  범위 k를 알 수 있는가? ──No──→ 기수 정렬 검토        │
│        │ Yes                                         │
│  k = O(n) 수준인가? ──No──→ 메모리 폭발 위험         │
│        │ Yes                                         │
│  계수 정렬 사용 ✅                                    │
└──────────────────────────────────────────────────────┘

📢 섹션 요약 비유: 계수 정렬을 쓸 때는 범위를 먼저 확인해야 한다. 100칸짜리 집계표는 편리하지만, 100억 칸짜리 집계표는 집 자체가 무너진다.

Ⅴ. 기대효과 및 결론

계수 정렬은 비교 연산을 아예 없애는 발상의 전환으로 이론적 하한을 돌파한다. 키 범위가 제한된 도메인(성적, 나이, 카테고리 코드)에서는 최고의 성능을 발휘하며, 기수 정렬의 핵심 서브루틴으로도 활약한다.

효과 정리

📢 섹션 요약 비유: 계수 정렬의 O(n+k)는 마치 번호표 시스템과 같다. 누가 먼저 왔는지 모두 비교하는 대신, 번호표를 나눠주고 번호 순서대로 부르면 된다. 번호 범위(k)가 합리적이면 이 방식이 압도적으로 빠르다.

📌 관련 개념 맵

📈 관련 키워드 및 발전 흐름도

[비교 기반 정렬(O(n log n) 하한)]
    │
    ▼
[계수 정렬(Counting Sort) — 값의 빈도 활용]
    │
    ▼
[누적 카운트 배열 — 위치 계산]
    │
    ▼
[안정성 보장 — 같은 값의 상대 순서 유지]
    │
    ▼
[기수 정렬(Radix Sort) 확장]

계수 정렬은 비교 기반 정렬의 한계를 넘어 누적 카운트와 안정성을 이용해 기수 정렬로 확장된다.

👶 어린이를 위한 3줄 비유 설명

🎫 번호표 받기: 마트 번호표처럼 각 숫자를 몇 번 봤는지 적어두면, 나중에 순서대로 꺼내기만 하면 돼요.
🗳️ 투표 집계: 후보를 하나씩 비교하지 않고, 각 후보마다 몇 표인지 세면 바로 순위를 알 수 있어요.
📊 칸막이 서랍: 0번부터 k번까지 서랍이 있고, 각 물건을 해당 번호 서랍에 넣으면 순서대로 꺼내기만 하면 정렬 완료!