비비교 정렬: Counting·Radix·Bucket Sort 선택 기준

비교 대신 키의 구조를 활용하는 정렬

원소끼리 대소를 비교하지 않고 키가 가진 범위, 자릿수, 분포를 이용하는 정렬 계열이 비비교 정렬이다. 조건이 맞으면 평균 시간복잡도 O(n) 수준에 도달할 수 있다.

대표적인 선택지는 Counting Sort, Radix Sort, Bucket Sort다. 세 알고리즘은 모두 입력 도메인에 대한 가정을 전제로 한다. 따라서 정렬 방식보다 먼저 키의 표현과 범위를 정해야 한다.

Counting Sort는 유한한 키 범위 [0..k)를 전제로 빈도와 누적합으로 각 원소의 위치를 구하는 안정 정렬이다. 시간·공간복잡도는 O(n + k)다.

Radix Sort는 기수 b와 자릿수 d를 기준으로 안정 정렬을 반복한다. 하위 자릿수부터 처리하는 LSD와 상위 자릿수부터 처리하는 MSD 방식이 있으며, 시간복잡도는 O(d · (n + b))다.

Bucket Sort는 값을 구간 또는 해시 기반 버킷으로 나눈 뒤 버킷 내부를 정렬한다. 균일한 분포를 가정하면 기대 시간복잡도는 O(n)이지만, 분포가 치우치면 성능이 떨어질 수 있다.

동일 키의 상대적 순서를 보존하는 안정성도 중요하다. Radix Sort는 안정적인 서브정렬, 일반적으로 Counting Sort를 사용해야 전체 정렬의 안정성을 유지할 수 있다.

키 표현과 메모리 한계를 먼저 모델링한다

정수 범위, 자릿수(b, d), 실수의 비트 재해석(예: IEEE 754)처럼 키를 어떤 형태로 다룰지 명시해야 한다. 음수 처리 방식, 오프셋(shift), 바이트 순서도 전처리 규칙으로 확정할 대상이다.

Counting Sort와 Radix Sort의 서브루틴은 보통 빈도 카운트, 누적합, 안정 배치 순서로 실행된다. 배열을 연속적으로 접근하고 분기를 줄일 수 있어 실제 성능을 다듬기에도 적합하다.

Bucket Sort는 버킷 수 B와 경계함수 f(x)를 어떻게 잡는지가 핵심이다. 샘플링으로 파라미터를 추정하고, 불균형 버킷에 대한 리밸런싱과 오버플로 대응도 준비해야 한다.

Counting/Radix는 추가 메모리 O(k) 또는 O(n + b)를 요구한다. 메모리가 제한된 환경에서는 기수 b나 버킷 수 B를 조정하거나 블록 처리(batch)를 고려할 수 있다. 예상 범위 k가 지나치게 크면 메모리 초과 위험이 있으므로 k 축소, 해싱, 다단계 처리 또는 비교 정렬 폴백이 필요하다. 분포 편향으로 Bucket Sort가 느려질 때는 동적 버킷 분할이나 임계치 기반 재버킷팅을 적용한다.

각 알고리즘이 배열을 배치하는 방식

Counting Sort의 누적 카운트

입력은 정수 배열 A, 키 범위 [min, max], 그리고 안정 정렬 여부다.

오프셋 = -min을 적용하고, k = max - min + 1 크기의 카운트 배열 C를 초기화한다.
A를 순회하며 C[키]를 증가시킨다.
C[i] = Σ C[0..i]가 되도록 누적합을 계산한다.
뒤에서 앞으로 원소를 읽으며 B[C[키]-1]에 배치하고 C[키]를 감소시킨다.

출력은 정렬된 배열 B다. k가 메모리 한계를 넘으면 Radix Sort, Bucket Sort 또는 비교 정렬로 폴백한다.

LSD Radix Sort의 자릿수 반복

입력은 정수 배열 A, 기수 b(예: 256), 자릿수 d, 안정 서브정렬이다.

자리 t = 0..d-1에 대해 반복한다.
각 원소에서 (A[i] // b^t) % b를 추출한다.
해당 자릿수를 Counting Sort로 안정 정렬한다.

음수가 포함되면 바이어스 또는 부호 분리가 필요하다. b가 지나치게 크면 캐시 미스가 늘어 성능이 저하될 수 있다.

Bucket Sort의 분포 기반 분할

입력은 실수 또는 해시 가능한 키 배열 A, 버킷 수 B, 버킷 경계함수 f다.

A[i]를 f로 매핑하고 버킷 b = f(A[i])에 넣는다.
각 버킷을 로컬 정렬한다. 소규모 버킷에는 삽입 정렬을, 일반적인 버킷에는 Timsort 또는 병합정렬을 쓸 수 있다.
버킷 순서대로 결과를 병합한다.

버킷 오버플로는 동적 확장 또는 보조 버킷으로 처리한다. 분포가 편향되면 B를 다시 조정하거나 2단계 버킷팅을 적용한다.

⤢✕

도메인 조건에 따른 선택

알고리즘	성능(시간)	확장성(도메인 제약)	일관성(안정성)	안정성(최악 케이스)	운영 편의
Counting Sort	O(n+k)	k 작을 때 우수, k 큰 경우 부적합	안정 정렬 기본 제공	범위 과대 시 메모리 실패 위험	구현 용이, 메모리 계획 필요
Radix Sort (LSD)	O(d·(n+b))	자릿수 고정, b 조정으로 확장	서브정렬 안정 필요	b 과대 시 캐시 미스, d 증가 시 반복 비용	구현 보통, 튜닝 필요
Bucket Sort	기대 O(n)	균일 분포 가정 시 우수	버킷 내부 정렬에 따름	분포 편향 시 O(n log n)로 악화	파라미터/분포 추정 필요
비교 정렬(Quick/Merge)	O(n log n)	도메인 제약 없음	구현에 따라 다름	Merge: 안정, Quick: 최악 O(n^2)	범용성 우수, 튜닝 부담 낮음

작은 정수 범위의 상태코드나 사용자 등급을 정렬할 때는 Counting Sort가 맞는다. 실시간 랭킹이나 빈도 기반 대시보드에도 적용할 수 있다.

32비트/64비트 정수 키로 구성된 정렬 파이프라인에는 Radix Sort(LSD, b=256)를 사용할 수 있다. 대규모 조인이나 그룹바이 전 정렬 기반 파이프라인의 스루풋 향상에 연결된다.

샘플링으로 균일 분포를 검증할 수 있다면 Bucket Sort로 1차 정렬을 수행하고, 버킷 내부를 Timsort로 마무리해 평균 지연시간을 줄일 수 있다. GPU나 멀티스레드 환경에서는 히스토그램·스캔(프리픽스 섬) 연산을 병렬화해 Radix/Counting 성능을 높일 수 있으며, NUMA 환경에서는 버킷을 소켓 로컬로 분배해 메모리 대역폭 병목을 완화할 수 있다.

성능 수치가 의미하는 범위

n=10^7, k=10^4인 정수 정렬에서는 Counting Sort의 연산량 O(10^7+10^4)가 비교 정렬의 O(n log2 n)≈2.3×10^8 비교 연산보다 우위를 가진다.

카운터를 4바이트로 두면 k=10^4에서 추가 메모리는 ≈ 40KB 수준이고, k=10^6에서는 ≈ 4MB 수준이다.

Radix Sort는 분기 없는 선형 접근으로 워스트 분산이 낮다. 안정 서브정렬을 사용하면 동일 키 데이터의 시맨틱을 보존해 후속 처리 품질도 유지할 수 있다. 범위와 자릿수가 고정된 도메인이라면 파라미터 재튜닝 빈도를 줄일 수 있고, 버킷 기반 파티셔닝과 결합하면 스케일아웃에도 유리하다.

파라미터와 폴백을 함께 설계한다

Radix Sort의 b는 2의 거듭제곱(예: 256)으로 잡으면 비트 마스킹 최적화를 적용할 수 있다. 다만 캐시 용량과 메모리 대역폭을 함께 봐야 한다. Bucket Sort의 B는 n의 제곱근 또는 메모리·코어 수를 기준으로 실험적으로 조정한다.

Counting Sort와 Radix Sort에서 음수는 오프셋 또는 부호 분리 후 병합하는 방식으로 처리한다. 실수 키는 키 스페이스 재해석(비트 캐스팅)이나 버킷 경계함수 설계가 필요하다.

k가 과도하게 크거나 분포가 편향됐거나 메모리가 타이트한 조건에서는 비교 정렬로 전환하는 하이브리드 파이프라인을 둔다. 사전 샘플링→파라미터 추정→실행→모니터링의 폐루프도 함께 운영한다.

Python 구현 예시

입력은 주로 비음수 정수 또는 [0,1) 범위 실수를 가정한다. 음수를 처리하려면 오프셋 또는 부호 분리를 추가해야 한다.

비음수 정수용 Counting Sort

def counting_sort(arr):
    if not arr:
        return []
    k = max(arr) + 1
    count = [0] * k
    for x in arr:
        count[x] += 1
    # 누적 합
    for i in range(1, k):
        count[i] += count[i-1]
    out = [0] * len(arr)
    # 안정 배치: 뒤에서 앞으로
    for x in reversed(arr):
        count[x] -= 1
        out[count[x]] = x
    return out

32비트 비음수 정수용 LSD Radix Sort

def radix_sort_lsd(arr):
    if not arr:
        return []
    out = arr[:]
    base = 256
    mask = base - 1
    for shift in (0, 8, 16, 24):
        count = [0] * base
        # 카운트
        for x in out:
            d = (x >> shift) & mask
            count[d] += 1
        # 누적 합
        for i in range(1, base):
            count[i] += count[i-1]
        # 안정 배치
        tmp = [0] * len(out)
        for x in reversed(out):
            d = (x >> shift) & mask
            count[d] -= 1
            tmp[count[d]] = x
        out = tmp
    return out

[0,1) 실수용 Bucket Sort

def bucket_sort(arr, B=None):
    n = len(arr)
    if n == 0:
        return []
    B = B or max(1, int(n ** 0.5))
    buckets = [[] for _ in range(B)]
    for x in arr:
        if not (0.0 <= x < 1.0):
            raise ValueError("입력은 [0,1) 범위 실수 가정")
        idx = min(B - 1, int(x * B))
        buckets[idx].append(x)
    out = []
    for b in buckets:
        b.sort()  # 파이썬 Timsort
        out.extend(b)
    return out