3-8. 정렬 알고리즘: Counting Sort (계수 정렬)

1. 계수 정렬(Counting Sort)의 개념과 배경

계수 정렬(Counting Sort)은 정렬 알고리즘 중 하나로, 특정한 상황에서 매우 효율적인 성능을 발휘합니다. 특히, 정렬하려는 데이터의 값들이 정수이고, 그 값들의 범위가 제한적일 때 뛰어난 속도를 보입니다. 이 알고리즘은 비교 기반 정렬 방식(예: 퀵 정렬, 병합 정렬)과는 달리, 각 원소의 비교 없이 정렬을 수행합니다. 대신, 데이터의 값 자체를 이용하여 정렬을 수행하기 때문에, 특정 조건에서 시간 복잡도를 획기적으로 줄일 수 있습니다.

계수 정렬의 기본적인 아이디어는 각 숫자가 몇 번 나타나는지 세는 것입니다. 예를 들어, [1, 4, 1, 2, 7, 5, 2] 와 같은 배열이 주어졌을 때, 각 숫자의 등장 횟수를 기록합니다. 그런 다음, 이 정보를 사용하여 정렬된 배열을 구성합니다.

계수 정렬은 정렬 알고리즘 중에서도 안정 정렬(stable sort)에 속합니다. 즉, 정렬 전 동일한 값을 가진 원소들의 상대적인 순서가 정렬 후에도 유지됩니다. 이는 특정 상황에서 중요한 특성이 될 수 있습니다.

2. 계수 정렬 알고리즘의 동작 원리

계수 정렬은 다음과 같은 단계로 진행됩니다.

1. 계수 배열(Counting Array) 초기화: 입력 배열에 있는 값들의 범위를 파악하여, 그 범위에 해당하는 크기의 계수 배열을 생성하고 0으로 초기화합니다. 계수 배열의 각 인덱스는 입력 배열의 값에 해당하며, 각 인덱스에 저장되는 값은 해당 값이 입력 배열에서 나타나는 횟수를 의미합니다.

2. 계수: 입력 배열을 순회하면서, 각 숫자가 나타나는 횟수를 계수 배열에 기록합니다. 예를 들어, 입력 배열의 값이 3이면, 계수 배열의 인덱스 3의 값을 1 증가시킵니다.

3. 누적 계수: 계수 배열을 순회하면서, 각 인덱스의 값을 해당 인덱스 이전의 모든 값의 합으로 변경합니다. 이렇게 하면 각 숫자가 정렬된 배열에서 어느 위치에 위치해야 하는지 알 수 있습니다.

4. 정렬: 입력 배열을 뒤에서부터 순회하면서, 각 숫자에 해당하는 계수 배열의 값을 확인합니다. 이 값을 통해 정렬된 배열에서 해당 숫자가 위치할 인덱스를 결정하고, 해당 위치에 숫자를 삽입합니다. 그리고 계수 배열의 해당 값을 1 감소시킵니다.

위 그림은 계수 정렬 알고리즘의 흐름을 시각적으로 보여줍니다. 각 단계별로 수행되는 작업을 명확하게 나타내어 알고리즘의 이해를 돕습니다.

3. 알고리즘 상세 설명 및 예제

다음은 계수 정렬 알고리즘을 좀 더 자세히 설명하고, 예제를 통해 각 단계를 자세히 살펴보겠습니다.

예제: [4, 2, 2, 8, 3, 3, 1]

1. 최댓값 찾기: 입력 배열에서 가장 큰 값(최댓값)을 찾습니다. 이 예제에서는 8입니다.

2. 계수 배열 생성: 최댓값을 기반으로 크기가 최댓값 + 1 인 계수 배열을 생성하고 0으로 초기화합니다. 이 경우, 계수 배열의 크기는 9가 됩니다.

   count = [0, 0, 0, 0, 0, 0, 0, 0, 0]

3. 계수: 입력 배열을 순회하면서 각 숫자의 등장 횟수를 계수 배열에 기록합니다.

   for i in arr: count[arr[i]] += 1

   결과:

   count = [1, 1, 2, 2, 1, 0, 0, 0, 1]

4. 누적 계수: 계수 배열을 순회하면서 각 인덱스의 값을 해당 인덱스 이전의 모든 값의 합으로 변경합니다.

   for i from 1 to len(count) - 1: count[i] += count[i-1]

   결과:

   count = [1, 2, 4, 6, 7, 7, 7, 7, 8] 5. 정렬: 입력 배열을 뒤에서부터 순회하면서 정렬된 배열을 생성합니다.

   sorted_arr = [0] * len(arr) for i from len(arr) - 1 to 0: index = count[arr[i]] - 1 sorted_arr[index] = arr[i] count[arr[i]] -= 1

   단계별 정렬 결과:

   • arr[6] <mark class="highlight"><strong><u> 1: index </u></strong></mark> count[1] - 1 <mark class="highlight"><strong><u> 1, sorted_arr[1] </u></strong></mark> 1, count[1] = 1
   • arr[5] <mark class="highlight"><strong><u> 3: index </u></strong></mark> count[3] - 1 <mark class="highlight"><strong><u> 5, sorted_arr[5] </u></strong></mark> 3, count[3] = 5
   • arr[4] <mark class="highlight"><strong><u> 3: index </u></strong></mark> count[3] - 1 <mark class="highlight"><strong><u> 4, sorted_arr[4] </u></strong></mark> 3, count[3] = 4
   • arr[3] <mark class="highlight"><strong><u> 8: index </u></strong></mark> count[8] - 1 <mark class="highlight"><strong><u> 7, sorted_arr[7] </u></strong></mark> 8, count[8] = 7
   • arr[2] <mark class="highlight"><strong><u> 2: index </u></strong></mark> count[2] - 1 <mark class="highlight"><strong><u> 3, sorted_arr[3] </u></strong></mark> 2, count[2] = 3
   • arr[1] <mark class="highlight"><strong><u> 2: index </u></strong></mark> count[2] - 1 <mark class="highlight"><strong><u> 2, sorted_arr[2] </u></strong></mark> 2, count[2] = 2
   • arr[0] <mark class="highlight"><strong><u> 4: index </u></strong></mark> count[4] - 1 <mark class="highlight"><strong><u> 6, sorted_arr[6] </u></strong></mark> 4, count[4] = 6

   최종 결과: [1, 2, 2, 3, 3, 4, 8]

4. 계수 정렬의 시간 복잡도와 공간 복잡도

계수 정렬은 입력 배열의 크기(n)와 입력 값의 범위(k)에 따라 시간 복잡도와 공간 복잡도가 결정됩니다.

• 시간 복잡도:
  • 최악, 평균, 최선의 경우 모두 O(n + k)입니다. 여기서 n은 입력 배열의 크기이고, k는 입력 값의 범위(최댓값 - 최솟값 + 1)입니다. 계수 배열을 생성하고, 입력 배열을 순회하고, 계수 배열을 누적하는 모든 단계가 O(n + k) 시간에 수행되기 때문입니다.
• 공간 복잡도: O(k)입니다. 계수 배열을 저장하기 위해 k만큼의 추가 공간이 필요합니다.

시간 복잡도가 O(n + k)이기 때문에, k가 n에 비해 크지 않다면 매우 효율적인 알고리즘입니다. 그러나 k가 n보다 훨씬 크면, 공간 낭비가 심해지고 효율성이 떨어질 수 있습니다.

5. 계수 정렬의 구현 (파이썬)

다음은 파이썬으로 구현된 계수 정렬 코드입니다.

def counting_sort(arr):
    """
    계수 정렬 알고리즘 구현.

    Args:
        arr: 정렬할 정수 배열.

    Returns:
        정렬된 배열.
    """
    if not arr:
        return []

    # 1. 입력 배열에서 최댓값과 최솟값 찾기
    min_val = min(arr)
    max_val = max(arr)

    # 2. 계수 배열 생성 및 초기화
    count_range = max_val - min_val + 1
    count = [0] * count_range

    # 3. 각 숫자의 등장 횟수 세기
    for num in arr:
        count[num - min_val] += 1

    # 4. 누적 계수 계산
    for i in range(1, count_range):
        count[i] += count[i - 1]

    # 5. 정렬된 배열 생성
    sorted_arr = [0] * len(arr)
    for num in reversed(arr):
        index = count[num - min_val] - 1
        sorted_arr[index] = num
        count[num - min_val] -= 1

    return sorted_arr

# 예제 사용
arr = [4, 2, 2, 8, 3, 3, 1]
sorted_arr = counting_sort(arr)
print(f"정렬된 배열: {sorted_arr}")

위 코드는 계수 정렬의 각 단계를 명확하게 보여줍니다. min_val과 max_val을 먼저 구하여 값의 범위를 파악하고, 이를 기반으로 계수 배열을 생성합니다. 입력 배열을 순회하며 각 숫자의 빈도수를 세고, 누적 계수를 계산한 후, 입력 배열을 역순으로 순회하며 정렬된 배열을 구성합니다.

6. 계수 정렬의 활용 사례

계수 정렬은 특정 조건에서 매우 유용하게 사용될 수 있습니다.

• 정수 정렬: 정수 데이터의 범위가 제한적인 경우 (예: 시험 점수, 나이), 계수 정렬은 퀵 정렬이나 병합 정렬보다 훨씬 빠를 수 있습니다.
• 데이터 빈도 분석: 데이터의 각 값의 빈도를 계산해야 하는 경우, 계수 배열을 활용하여 쉽게 분석할 수 있습니다.
• 기수 정렬의 서브 루틴: 계수 정렬은 기수 정렬(Radix Sort)의 서브 루틴으로 사용될 수 있습니다. 기수 정렬은 여러 자리수의 정수를 정렬할 때 각 자리수별로 계수 정렬을 수행합니다.

7. 계수 정렬의 주의사항과 개선 방안

계수 정렬은 몇 가지 주의사항이 있습니다.

• 값의 범위: 입력 값의 범위가 넓으면 계수 배열의 크기가 커져서 공간 낭비가 발생할 수 있습니다.
• 음수 값 처리: 음수 값이 포함된 경우, 입력 값의 최솟값을 고려하여 계수 배열의 인덱스를 조정해야 합니다. 위 파이썬 코드에서는 이를 min_val을 이용하여 처리했습니다.
• 실수 값 처리: 실수 값에는 사용할 수 없습니다. 실수 값의 경우, 값의 범위가 무한대에 가깝고, 각 값을 인덱스로 사용할 수 없기 때문입니다.

계수 정렬의 개선 방안은 다음과 같습니다.

• 메모리 최적화: 입력 값의 범위가 넓지만, 실제로 데이터가 분포된 범위가 좁은 경우, 희소 배열(sparse array)과 같은 자료구조를 사용하여 메모리 사용량을 줄일 수 있습니다.
• 병렬 처리: 계수 배열을 생성하고 누적하는 과정은 병렬 처리가 가능합니다. 멀티 스레딩이나 분산 컴퓨팅 환경에서 성능을 향상시킬 수 있습니다.

8. 계수 정렬 vs. 다른 정렬 알고리즘

계수 정렬은 다른 정렬 알고리즘과 비교하여 다음과 같은 특징을 보입니다.

계수 정렬은 정렬하려는 데이터의 특성에 따라 다른 알고리즘보다 훨씬 더 효율적일 수 있습니다. 데이터의 값의 범위가 좁고 정수형 데이터인 경우 계수 정렬을 고려해 볼 만합니다.

9. 결론

계수 정렬은 정렬 알고리즘 중에서도 특별한 경우에 매우 강력한 성능을 발휘하는 알고리즘입니다. 데이터의 값의 범위가 제한적이고 정수형 데이터일 경우, 시간 복잡도 O(n + k)를 달성하여 다른 정렬 알고리즘보다 훨씬 빠르게 정렬할 수 있습니다. 하지만, 값의 범위가 넓거나 실수형 데이터에는 적용하기 어렵다는 단점도 있습니다. 계수 정렬의 원리를 이해하고, 실제 상황에 적용하여 효율적인 정렬을 수행할 수 있도록 노력해야 합니다.