정렬 알고리즘 (Sorting Algorithms) - 카운팅 정렬 (Counting Sort)

Counting 정렬 (Counting Sort)

Counting Sort는 특정 조건에서 효율적인 정렬 알고리즘으로, 비교 기반 정렬 알고리즘이 아닙니다. 배열의 각 항목의 빈도를 기반으로 정렬하며, 원소의 범위가 제한적이고 양의 정수인 경우 매우 효율적입니다.

---

1. 작동 원리

1. 범위 설정: 정렬할 배열에서 가장 큰 값을 찾아, 모든 값을 표현할 수 있는 범위를 설정합니다.
2. 빈도 계산: 각 원소의 빈도를 저장하는 count 배열을 만듭니다.
3. 누적 계산: count 배열을 기반으로 누적합을 계산하여 정렬된 배열에서 각 원소의 최종 위치를 결정합니다.
4. 결과 저장: 정렬된 값을 새로운 배열에 저장합니다.

---

2. 특징

• 시간 복잡도: O(n + k)
  • n: 입력 배열의 크기
  • k: 데이터의 범위 (최대값 - 최소값)
• 공간 복잡도: O(n + k) (추가 공간 필요)
• 제한 사항:
  • 정수 또는 정수로 표현 가능한 데이터에만 사용 가능.
  • 데이터 범위가 크면 비효율적.
• 안정성: 원소의 순서를 유지하기 때문에 안정 정렬입니다.

---

3. 단계별 예제

입력 배열: [4, 2, 2, 8, 3, 3, 1]

1. 빈도 계산:
   • count 배열 생성: [0, 1, 2, 2, 1, 0, 0, 0, 1]
     • 각 인덱스는 숫자, 값은 빈도.
2. 누적합 계산:
   • count 배열 누적합: [0, 1, 3, 5, 6, 6, 6, 6, 7]
     • 누적합은 원소가 최종적으로 위치할 인덱스 정보를 제공합니다.
3. 정렬 배열 생성:
   • 입력 배열을 역순으로 순회하며 정렬된 배열에 저장:
     • 결과: [1, 2, 2, 3, 3, 4, 8]

---

4. 장점과 단점

장점:

1. 선형 시간 복잡도: 비교 기반 정렬보다 빠른 성능 (O(n)).
2. 안정 정렬: 원소의 상대적인 순서를 유지.

단점:

1. 추가 메모리 사용량: 데이터 범위가 클수록 많은 메모리 필요.
2. 제한적인 데이터: 정수 또는 정수형으로 매핑 가능한 값에만 사용.

---

5. Java 구현

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {
        if (arr.length == 0) {
            return;
        }

        // Step 1: Find the range of the array
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Arrays.stream(arr).min().getAsInt();
        int range = max - min + 1;

        // Step 2: Create count array and output array
        int[] count = new int[range];
        int[] output = new int[arr.length];

        // Step 3: Count occurrences of each number
        for (int num : arr) {
            count[num - min]++;
        }

        // Step 4: Compute cumulative count
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }

        // Step 5: Place elements into output array in sorted order
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }

        // Step 6: Copy sorted array back to the original array
        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("Original Array: " + Arrays.toString(arr));

        countingSort(arr);

        System.out.println("Sorted Array: " + Arrays.toString(arr));
    }
}

---

6. Python 구현

def counting_sort(arr):
    if not arr:
        return arr

    # Step 1: Find the range of the array
    min_val = min(arr)
    max_val = max(arr)
    range_val = max_val - min_val + 1

    # Step 2: Create count array and output array
    count = [0] * range_val
    output = [0] * len(arr)

    # Step 3: Count occurrences of each number
    for num in arr:
        count[num - min_val] += 1

    # Step 4: Compute cumulative count
    for i in range(1, len(count)):
        count[i] += count[i - 1]

    # Step 5: Place elements into output array in sorted order
    for num in reversed(arr):
        output[count[num - min_val] - 1] = num
        count[num - min_val] -= 1

    return output

# Example usage
if __name__ == "__main__":
    arr = [4, 2, 2, 8, 3, 3, 1]
    print("Original Array:", arr)

    sorted_arr = counting_sort(arr)

    print("Sorted Array:", sorted_arr)

---

7. 활용 사례

1. 데이터 범위가 제한적이고 양의 정수인 경우:
   • 예: 성적 분포 정렬, 특정 범위의 로그 데이터를 정렬.
2. 빠른 정렬이 필요한 경우:
   • 데이터의 크기는 크지만 값의 범위가 작을 때 효과적.
3. 실시간 시스템:
   • 예측 가능한 실행 시간이 중요한 응용 프로그램.

Counting 정렬은 효율적이지만, 메모리와 데이터 유형의 제약으로 인해 특정 상황에서만 유용합니다.