[알고리즘 이론] 계수 정렬(Counting Sort)

728x90

1. 계수 정렬이란?

계수 정렬(Counting Sort)은 비교 기반이 아닌 정렬 알고리즘으로, 정수나 정수로 표현할 수 있는 데이터를 정렬할 때 사용됩니다. 이 알고리즘은 각 항목이 몇 번 등장하는지 세어서 정렬하는 방식으로 작동합니다. 특히 정수의 범위가 작을 때 매우 효율적인 알고리즘입니다.

2. 계수 정렬의 기본 원리

계수 정렬의 기본 아이디어는 다음과 같습니다:

입력 배열의 최댓값과 최솟값을 찾아 범위를 결정합니다.
해당 범위만큼의 크기를 가진 카운트 배열을 생성합니다.
입력 배열을 순회하며 각 요소의 출현 횟수를 카운트 배열에 기록합니다.
카운트 배열을 누적합으로 변환합니다(선택 사항).
누적합을 이용하여 각 요소의 정확한 위치를 계산하고 결과 배열에 배치합니다.

3. 계수 정렬 알고리즘 단계별 설명

계수 정렬 알고리즘의 기본적인 단계는 다음과 같습니다:

입력 배열에서 최댓값과 최솟값을 찾습니다.
최댓값 크기의 카운트 배열을 생성합니다.
입력 배열을 순회하며 각 요소의 출현 횟수를 카운트 배열에 기록합니다.
카운트 배열을 이용해 정렬된 배열을 생성합니다.
안정적 정렬을 위해 누적합을 사용할 수 있습니다.

다음 섹션에서는 자바와 파이썬으로 구현한 계수 정렬 코드를 살펴보겠습니다.

4. 자바로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

import java.util.Arrays;

public class CountingSort {
    public static void countingSort(int[] arr) {
        // 1. 배열의 최댓값 찾기
        int max = Arrays.stream(arr).max().getAsInt();
        
        // 2. 카운트 배열 생성 (0부터 max까지의 인덱스)
        int[] count = new int[max + 1];
        
        // 3. 각 요소의 출현 횟수 세기
        for (int num : arr) {
            count[num]++;
        }
        
        // 4. 카운트 배열을 기반으로 정렬된 배열 생성
        int index = 0;
        for (int i = 0; i <= max; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }
    
    // 테스트를 위한 메인 메소드
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("정렬 전: " + Arrays.toString(arr));
        countingSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
}

안정적인 버전(누적합 기반)

import java.util.Arrays;

public class StableCountingSort {
    public static void stableCountingSort(int[] arr) {
        // 1. 배열의 최댓값 찾기
        int max = Arrays.stream(arr).max().getAsInt();
        
        // 2. 카운트 배열 생성
        int[] count = new int[max + 1];
        
        // 3. 요소의 출현 횟수 세기
        for (int num : arr) {
            count[num]++;
        }
        
        // 4. 누적합 계산
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        
        // 5. 결과 배열 생성
        int[] output = new int[arr.length];
        
        // 6. 뒤에서부터 순회하여 안정적 정렬 보장
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;
        }
        
        // 7. 결과 배열을 원래 배열에 복사
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
    
    // 테스트를 위한 메인 메소드
    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        System.out.println("정렬 전: " + Arrays.toString(arr));
        stableCountingSort(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
}

음수를 포함한 계수 정렬(자바)

import java.util.Arrays;

public class CountingSortWithNegatives {
    public static void countingSortWithNegatives(int[] arr) {
        // 1. 배열의 최댓값과 최솟값 찾기
        int min = Arrays.stream(arr).min().getAsInt();
        int max = Arrays.stream(arr).max().getAsInt();
        
        // 2. 카운트 배열 생성 (min에서 max까지의 범위)
        int range = max - min + 1;
        int[] count = new int[range];
        
        // 3. 각 요소의 출현 횟수 세기 (min을 오프셋으로 사용)
        for (int num : arr) {
            count[num - min]++;
        }
        
        // 4. 카운트 배열을 기반으로 정렬된 배열 생성
        int index = 0;
        for (int i = 0; i < range; i++) {
            while (count[i] > 0) {
                arr[index++] = i + min; // min을 다시 더해 원래 값 복원
                count[i]--;
            }
        }
    }
    
    // 테스트를 위한 메인 메소드
    public static void main(String[] args) {
        int[] arr = {-5, -10, 0, -3, 8, 5, -1, 10};
        System.out.println("정렬 전: " + Arrays.toString(arr));
        countingSortWithNegatives(arr);
        System.out.println("정렬 후: " + Arrays.toString(arr));
    }
}

5. 파이썬으로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

def counting_sort(arr):
    # 1. 배열의 최댓값 찾기
    max_val = max(arr)
    
    # 2. 카운트 배열 생성 (0부터 max까지의 인덱스)
    count = [0] * (max_val + 1)
    
    # 3. 각 요소의 출현 횟수 세기
    for num in arr:
        count[num] += 1
    
    # 4. 카운트 배열을 기반으로 정렬된 배열 생성
    sorted_arr = []
    for i in range(len(count)):
        sorted_arr.extend([i] * count[i])
    
    return sorted_arr

# 테스트
if __name__ == "__main__":
    arr = [4, 2, 2, 8, 3, 3, 1]
    print(f"정렬 전: {arr}")
    sorted_arr = counting_sort(arr)
    print(f"정렬 후: {sorted_arr}")

안정적인 버전(누적합 기반)

def stable_counting_sort(arr):
    # 1. 배열의 최댓값 찾기
    max_val = max(arr)
    
    # 2. 카운트 배열 생성
    count = [0] * (max_val + 1)
    
    # 3. 요소의 출현 횟수 세기
    for num in arr:
        count[num] += 1
    
    # 4. 누적합 계산
    for i in range(1, len(count)):
        count[i] += count[i - 1]
    
    # 5. 결과 배열 생성
    output = [0] * len(arr)
    
    # 6. 뒤에서부터 순회하여 안정적 정렬 보장
    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
    
    return output

# 테스트
if __name__ == "__main__":
    arr = [4, 2, 2, 8, 3, 3, 1]
    print(f"정렬 전: {arr}")
    sorted_arr = stable_counting_sort(arr)
    print(f"정렬 후: {sorted_arr}")

음수를 포함한 계수 정렬(파이썬)

def counting_sort_with_negatives(arr):
    # 1. 배열의 최댓값과 최솟값 찾기
    min_val = min(arr)
    max_val = max(arr)
    
    # 2. 카운트 배열 생성 (min에서 max까지의 범위)
    range_val = max_val - min_val + 1
    count = [0] * range_val
    
    # 3. 각 요소의 출현 횟수 세기 (min을 오프셋으로 사용)
    for num in arr:
        count[num - min_val] += 1
    
    # 4. 카운트 배열을 기반으로 정렬된 배열 생성
    sorted_arr = []
    for i in range(range_val):
        sorted_arr.extend([i + min_val] * count[i])
    
    return sorted_arr

# 테스트
if __name__ == "__main__":
    arr = [-5, -10, 0, -3, 8, 5, -1, 10]
    print(f"정렬 전: {arr}")
    sorted_arr = counting_sort_with_negatives(arr)
    print(f"정렬 후: {sorted_arr}")

6. 계수 정렬의 시간 복잡도 및 공간 복잡도

시간 복잡도

최악의 경우: O(n + k)
평균: O(n + k)
최선의 경우: O(n + k)

여기서 n은 입력 배열의 크기이고, k는 입력 배열의 최댓값과 최솟값의 차이(범위)입니다.

공간 복잡도

O(n + k)

카운트 배열과 출력 배열을 위한 추가 공간이 필요합니다.

7. 계수 정렬의 장단점

장점

특정 조건에서 매우 빠른 정렬 속도 (O(n + k))
비교 기반 정렬 알고리즘의 이론적 하한인 O(n log n)보다 빠를 수 있음
안정적인 정렬 알고리즘(동일한 값의 상대적 순서가 유지됨)

단점

정수나 정수로 표현 가능한 데이터에만 적용 가능
데이터의 범위가 클 경우 메모리 낭비가 심함
음수를 처리하기 위해서는 추가적인 처리 필요

8. 음수를 포함한 계수 정렬

기본 계수 정렬은 음수를 처리할 수 없지만, 약간의 수정으로 음수도 처리할 수 있습니다. 앞서 자바와 파이썬으로 구현한 음수 처리 버전을 다시 한번 살펴보겠습니다.

이 알고리즘의 핵심은 최솟값을 오프셋으로 사용하여 모든 값을 양수로 변환한 후, 다시 원래 값으로 복원하는 것입니다.

9. 계수 정렬의 응용 예제

문자열 정렬 (자바)

계수 정렬은 문자열을 정렬하는 데에도 활용할 수 있습니다. 예를 들어, 소문자 알파벳만으로 구성된 문자열을 정렬하는 경우:

public static void sortCharacters(char[] arr) {
    // 알파벳 소문자는 26개
    int[] count = new int[26];
    
    // 각 문자의 출현 횟수 세기 ('a'를 오프셋으로 사용)
    for (char c : arr) {
        count[c - 'a']++;
    }
    
    // 정렬된 결과 생성
    int index = 0;
    for (int i = 0; i < 26; i++) {
        char currentChar = (char) ('a' + i);
        while (count[i] > 0) {
            arr[index++] = currentChar;
            count[i]--;
        }
    }
}

문자열 정렬 (파이썬)

def sort_characters(chars):
    # 알파벳 소문자는 26개
    count = [0] * 26
    
    # 각 문자의 출현 횟수 세기 ('a'를 오프셋으로 사용)
    for c in chars:
        count[ord(c) - ord('a')] += 1
    
    # 정렬된 결과 생성
    result = []
    for i in range(26):
        current_char = chr(ord('a') + i)
        result.extend([current_char] * count[i])
    
    return result

# 테스트
if __name__ == "__main__":
    chars = list("programming")
    print(f"정렬 전: {''.join(chars)}")
    sorted_chars = sort_characters(chars)
    print(f"정렬 후: {''.join(sorted_chars)}")

학생 점수 분포 계산 (자바)

계수 정렬은 데이터 분석에서도 유용하게 사용됩니다. 예를 들어, 학생들의 시험 점수 분포를 계산할 때:

public static void analyzeScores(int[] scores) {
    // 점수는 0-100 범위
    int[] distribution = new int[101];
    
    // 각 점수의 빈도 계산
    for (int score : scores) {
        distribution[score]++;
    }
    
    // 점수 분포 출력
    for (int i = 0; i <= 100; i++) {
        if (distribution[i] > 0) {
            System.out.println("점수 " + i + ": " + distribution[i] + "명");
        }
    }
}

학생 점수 분포 계산 (파이썬)

def analyze_scores(scores):
    # 점수는 0-100 범위
    distribution = [0] * 101
    
    # 각 점수의 빈도 계산
    for score in scores:
        distribution[score] += 1
    
    # 점수 분포 출력
    for i in range(101):
        if distribution[i] > 0:
            print(f"점수 {i}: {distribution[i]}명")

# 테스트
if __name__ == "__main__":
    scores = [85, 92, 78, 65, 92, 85, 100, 77, 85, 92]
    analyze_scores(scores)

10. 실제 사용 사례

빈도 분석: 텍스트 분석, 데이터 압축(허프만 코딩) 등에서 문자 빈도 계산
기수 정렬(Radix Sort)의 서브루틴: 더 큰 범위의 정수를 정렬하는 기수 정렬의 내부 알고리즘으로 사용
네트워크 패킷 분석: IP 주소나 포트 번호와 같은 제한된 범위의 값들을 정렬할 때
히스토그램 생성: 이미지 처리에서 픽셀 값의 분포를 계산할 때

11. 다른 정렬 알고리즘과의 비교

알고리즘 시간 복잡도 (평균) 공간 복잡도 안정성 비고

계수 정렬	O(n + k)	O(n + k)	안정적	범위가 작은 정수에 효율적
퀵 정렬	O(n log n)	O(log n)	불안정	평균적으로 빠르지만 최악의 경우 O(n²)
병합 정렬	O(n log n)	O(n)	안정적	항상 일정한 성능 보장
힙 정렬	O(n log n)	O(1)	불안정	제자리 정렬 가능
기수 정렬	O(d * (n + k))	O(n + k)	안정적	여러 자릿수 정수에 효율적

12. 결론

계수 정렬은 특정 조건에서 매우 효율적인 정렬 알고리즘입니다. 데이터의 범위가 작고 정수형 데이터일 때는 비교 기반 정렬 알고리즘보다 훨씬 빠른 성능을 보입니다. 하지만 데이터의 범위가 크거나 부동 소수점 수와 같은 비정수 데이터에는 적합하지 않습니다.

실제 알고리즘 설계에서는 데이터의 특성과 제약 조건을 고려하여 적절한 정렬 알고리즘을 선택하는 것이 중요합니다. 계수 정렬은 그 특별한 용도와 한계를 이해하고 적절히 활용할 때 진가를 발휘합니다.

728x90

'알고리즘 > 이론' 카테고리의 다른 글

[Leetcode]932. Beautiful Array (2)	2025.05.14
[알고리즘 이론] 분할 정복(Divide and Conquer) (0)	2025.05.14
[알고리즘 이론] 위상 정렬(Topological Sorting) (0)	2025.04.22
[알고리즘 이론] 큐(Queue) (0)	2025.03.21
[알고리즘 이론] 투 포인터(Two Pointers) (0)	2024.10.02

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

일지 & 개발

[알고리즘 이론] 계수 정렬(Counting Sort)

1. 계수 정렬이란?

2. 계수 정렬의 기본 원리

3. 계수 정렬 알고리즘 단계별 설명

4. 자바로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

안정적인 버전(누적합 기반)

음수를 포함한 계수 정렬(자바)

5. 파이썬으로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

안정적인 버전(누적합 기반)

음수를 포함한 계수 정렬(파이썬)

6. 계수 정렬의 시간 복잡도 및 공간 복잡도

시간 복잡도

공간 복잡도

7. 계수 정렬의 장단점

장점

단점

8. 음수를 포함한 계수 정렬

9. 계수 정렬의 응용 예제

문자열 정렬 (자바)

문자열 정렬 (파이썬)

학생 점수 분포 계산 (자바)

학생 점수 분포 계산 (파이썬)

10. 실제 사용 사례

11. 다른 정렬 알고리즘과의 비교

12. 결론

'알고리즘 > 이론' 카테고리의 다른 글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

[알고리즘 이론] 계수 정렬(Counting Sort)

1. 계수 정렬이란?

2. 계수 정렬의 기본 원리

3. 계수 정렬 알고리즘 단계별 설명

4. 자바로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

안정적인 버전(누적합 기반)

음수를 포함한 계수 정렬(자바)

5. 파이썬으로 구현한 계수 정렬

기본 버전(출현 횟수 기반)

안정적인 버전(누적합 기반)

음수를 포함한 계수 정렬(파이썬)

6. 계수 정렬의 시간 복잡도 및 공간 복잡도

시간 복잡도

공간 복잡도

7. 계수 정렬의 장단점

장점

단점

8. 음수를 포함한 계수 정렬

9. 계수 정렬의 응용 예제

문자열 정렬 (자바)

문자열 정렬 (파이썬)

학생 점수 분포 계산 (자바)

학생 점수 분포 계산 (파이썬)

10. 실제 사용 사례

11. 다른 정렬 알고리즘과의 비교

12. 결론

'알고리즘 > 이론' 카테고리의 다른 글

관련글

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역