포스트

안정 계수 정렬(Stable Counting Sort)의 원리와 역방향 순회

게시
By woolam
조회 13 분읽는 시간
안정 계수 정렬(Stable Counting Sort)의 원리와 역방향 순회

“한 줄 요약: 비교 없이 위치를 계산하여 정렬하되, 입력 순서를 끝까지 지켜내는 알고리즘”

1. 계수 정렬(Counting Sort)이란?

일반적인 정렬(Quick, Merge 등)이 데이터끼리 크기를 직접 비교하는 것과 달리 계수 정렬은 각 숫자가 몇 번 등장했는지를 카운팅하여 위치를 찾아주는 알고리즘입니다.

  • 핵심 원리: 데이터의 값을 직접 비교하지 않고 각 값이 몇 개인지 저장하는 ‘카운팅 배열’을 만들어 정렬합니다.
  • 장점: 데이터의 범위가 작을 때 어떤 비교 정렬보다도 빠른 $O(n + k)$ (k는 데이터의 최대값)의 시간 복잡도를 가집니다.

2. 왜 ‘안정성(Stability)’이 필요한가?

단순히 숫자의 개수를 세어서 순서대로 출력하는 ‘계수 정렬’은 정렬은 되지만 원래 데이터가 가지고 있던 순서 정보는 잃어버립니다. 만약 ‘점수가 같은 학생들 중에서는 먼저 접수한 학생이 앞에 오게’ 정렬하고 싶다면 반드시 동일한 값들의 상대적 순서를 유지하는 안정 정렬(Stable Sort) 을 사용해야 합니다.

3. 안정 계수 정렬의 4단계 프로세스

안정성을 확보한 계수 정렬의 단계는 다음과 같습니다.

  1. 빈도수 계산 (Counting): 입력 배열을 순회하며 각 숫자가 몇 번 나타나는지 카운팅 배열에 기록합니다.
  2. 누적합 계산 (Cumulative Sum): 카운팅 배열의 각 요소를 현재 값 + 이전 값으로 업데이트합니다. 이 누적합은 “해당 숫자가 결과 배열에서 들어갈 수 있는 마지막 위치” 를 의미하게 됩니다.
  3. 뒤에서부터 배치 (Stable Placement) - 핵심!: 입력 배열의 마지막 원소부터 거꾸로 확인하며 결과 배열에 배치합니다. (상세 이유는 4번 문단 참고)
  4. 카운팅 감소: 원소를 하나 배치할 때마다 카운팅 배열의 해당 인덱스 값을 1씩 줄여 다음 원소가 그 앞 칸에 들어갈 수 있도록 합니다.

Java 구현 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public class CountingSort {
    public int[] sort(int[] array, int maxRange) {
        int n = array.length;
        int[] result = new int[n]; // 정렬된 결과를 담을 배열
        int[] cumulative = new int[maxRange + 1]; // 빈도수 및 누적합을 담을 배열

        // 1. 빈도수 계산
        for (int i = 0; i < n; i++) {
            cumulative[array[i]]++;
        }

        // 2. 누적합 계산 (각 숫자의 위치 확정)
        for (int i = 1; i <= maxRange; i++) {
            cumulative[i] += cumulative[i - 1];
        }

        // 3. 안정성을 위해 뒤에서부터 순회하며 배치
        for (int i = n - 1; i >= 0; i--) {
            int value = array[i];
            int position = cumulative[value] - 1; // 인덱스는 0부터 시작하므로 -1
            result[position] = value;
            
            // 4. 다음 동일한 숫자를 위해 위치(인덱스) 감소
            cumulative[value]--;
        }
    }
}

4. 왜 ‘뒤에서부터’ 채워야 할까?

안정 계수 정렬의 로직에서 가장 중요한 부분이 바로 for (int i = n - 1; i >= 0; i--) 즉 역방향 순회입니다.

1) 누적합은 ‘경계선’이다

카운팅 배열을 누적합으로 만들고 나면 각 숫자는 자신이 들어갈 수 있는 영역의 ‘가장 오른쪽 끝(마지막 인덱스)’ 을 가리키게 됩니다.

  • 예: 숫자 5의 누적합이 10이라면 숫자 5는 결과 배열의 9번 인덱스까지 차지할 수 있다는 뜻입니다.

2) 순서 보존의 메커니즘 (Last-In, Last-Out)

입력 배열에 값이 같은 $A_1$(앞쪽)과 $A_2$(뒤쪽)가 있다고 가정해 보겠습니다.

  • 역방향 순회 시: 우리는 $A_2$를 먼저 만납니다. 누적합이 알려준 ‘가장 오른쪽 빈칸’에 $A_2$를 넣습니다. 그 후 하나 앞 칸에 $A_1$이 들어갑니다.
    • 결과: 뒤에 있던 $A_2$가 결과에서도 뒤에 위치합니다. (안정성 유지)
  • 순방향 순회 시: 우리가 $A_1$을 먼저 만납니다. 누적합이 알려준 ‘가장 오른쪽 빈칸’에 $A_1$을 넣습니다. 그 후 뒤따라온 $A_2$는 $A_1$의 앞 칸에 들어가게 됩니다.
    • 결과: 원래 앞에 있던 $A_1$이 뒤로 밀려 순서가 뒤바뀝니다. (안정성 파괴)

💡 핵심: 누적합이 ‘마지막 위치’ 를 알려주기 때문에 그 위치에 가장 먼저 어울리는 데이터는 입력 배열에서도 가장 마지막에 있던 데이터여야 합니다.

5. 주의사항 및 한계 (feat. 인덱스 오프셋)

1) 데이터 타입 제한과 ‘인덱스 오프셋(Offset)’

계수 정렬은 배열의 인덱스를 직접 사용하기 때문에 음수를 바로 인덱스로 쓸 수 없습니다(예: count[-5]는 에러). 이때 사용하는 기법이 인덱스 오프셋입니다.

  • 원리: 데이터의 최솟값(min)을 찾아 모든 데이터에서 min을 차감하는 데이터 정규화(Normalization) 과정을 거칩니다.
  • 설명: 이를 통해 실제 데이터가 어떤 범위에 있든 상관없이 인덱스의 시작점을 0으로 리베이스(Rebase) 하여 배열 구조에 완벽하게 매핑할 수 있습니다.
  • 예시: 최솟값이 -3인 데이터들을 정렬할 때:
    • -3 (데이터) - -3 (최솟값) = 0번 인덱스
    • -1 (데이터) - -3 (최솟값) = 2번 인덱스
    • 2 (데이터) - -3 (최솟값) = 5번 인덱스
  • 결과: 음수 영역의 데이터들도 0 이상의 배열 인덱스로 안전하게 매핑하여 카운팅할 수 있습니다.

2) 메모리 낭비

데이터의 범위($max - min + 1$)가 너무 크면 비효율적입니다. 예를 들어 1과 10억 단 두 개를 정렬하기 위해 10억 칸짜리 배열을 만드는 상황이 발생할 수 있습니다.

6. 음수 대응 가능 안정 계수 정렬 코드 (Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

/**
 * 안정성을 보장하는 계수 정렬 (Stable Counting Sort)
 * 음수 데이터를 처리하기 위해 '데이터 정규화(Normalization)' 기법을 적용
 */
public int[] stableCountingSortWithOffset(int[] array) {
    if (array.length == 0) return array;

    // 1. 데이터의 범위를 파악하기 위해 최솟값(min)과 최댓값(max) 탐색
    int min = array[0], max = array[0];
    for (int num : array) {
        if (num < min) min = num;
        if (num > max) max = num;
    }

    // 데이터가 차지하는 전체 범위를 계산하여 카운팅 배열 크기 결정
    int range = max - min + 1;
    int[] cumulative = new int[range];
    int[] result = new int[array.length];

    // 2. 빈도수 계산 (데이터 정규화 적용)
    // 배열 인덱스는 음수를 허용하지 않으므로 모든 값에서 min을 차감하여 
    // 0부터 시작하는 인덱스 체계로 '리베이스(Rebase)'
    for (int value : array) {
        cumulative[value - min]++;
    }

    // 3. 누적합 계산 (각 숫자가 들어갈 영역의 '오른쪽 경계선' 설정)
    for (int i = 1; i < range; i++) {
        cumulative[i] += cumulative[i - 1];
    }

    // 4. 안정성을 위해 역방향 순회하며 배치
    for (int i = array.length - 1; i >= 0; i--) {
        int value = array[i];
        
        // 정규화된 인덱스(value - min)를 사용하여 누적합 배열에 접근
        // position은 해당 숫자가 들어갈 수 있는 가장 우측 인덱스
        int position = cumulative[value - min] - 1; 
        result[position] = value;
        
        // 동일한 숫자가 또 나올 경우를 대비해 위치를 하나 앞으로 당김
        cumulative[value - min]--;
    }

    return result;
}

7. 오늘의 회고: 당연한 로직 뒤에 숨은 의도

  • 깨달은 점: 처음에는 i = n - 1부터 시작하는 코드를 보고 단순히 “그냥 관습인가?”라고 생각했습니다. 하지만 직접 손으로 데이터 위치를 그려보니 누적합이 ‘마지막 위치’를 가리키기 때문에 순서를 지키려면 뒤에 있는 데이터를 마지막 칸에 먼저 넣어줘야 한다는 사실을 깨달았습니다.
  • 반성: 알고리즘의 동작 결과에만 집중하느라 그 과정을 설계한 의도(Design Intent) 를 놓치고 있었습니다. 안정 정렬은 단순히 정렬을 넘어 데이터의 기록을 보존하는 방식이라는 점이 인상 깊습니다.
  • 다짐: 앞으로 어떤 코드를 보든 “왜 이 방향인가?” “왜 이 자료구조인가?”라는 질문을 스스로에게 던지며 의도를 파악하는 습관을 들여야겠습니다.

📚 References

본 포스팅은 알고리즘의 표준 가이드와 자료를 바탕으로 작성되었습니다.

  • Thomas H. Cormen: Introduction to Algorithms (CLRS) - Section 8.2 Counting Sort
  • GeeksforGeeks: Counting Sort Algorithm
Algorithm, Java
Sorting CountingSort Stability Algorithm
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.