3-7. 정렬 알고리즘: 기수 정렬

1. 기수 정렬의 개념과 배경

정렬 알고리즘은 컴퓨터 과학의 가장 기본적인 문제 중 하나이며, 데이터 처리의 효율성을 크게 좌우합니다. 우리가 흔히 접하는 정렬 알고리즘에는 비교 기반 정렬(Comparison-based sorting) 방식이 있습니다. 선택 정렬, 버블 정렬, 삽입 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 등이 이에 해당합니다. 비교 기반 정렬은 각 요소 간의 상대적인 크기를 비교하여 정렬을 수행하며, 이론적으로 $O(n \log n)$ 시간 복잡도 이상의 성능을 낼 수 없습니다.

하지만, 특정 조건에서는 비교 연산을 사용하지 않고 더 빠른 속도로 정렬할 수 있는 방법이 있습니다. 그중 하나가 바로 기수 정렬(Radix Sort)입니다. 기수 정렬은 정수나 문자열과 같이, 각 자릿수(digit) 또는 문자(character) 단위로 정렬할 수 있는 데이터에 특화된 알고리즘입니다. 기수 정렬은 비교 연산을 사용하지 않기 때문에, 비교 기반 정렬 알고리즘이 가지는 $O(n \log n)$ 시간 복잡도의 제약에서 벗어날 수 있습니다.

1) 기수 정렬의 배경

기수 정렬은 19세기 말, Herman Hollerith에 의해 고안되었습니다. Hollerith는 미국 인구 조사의 데이터를 처리하기 위해 펀치 카드(Punch card)를 사용했습니다. 펀치 카드는 각 열에 숫자를 나타내는 구멍이 뚫려 있었고, Hollerith는 각 열을 기준으로 카드를 분류하여 데이터를 정렬했습니다. 이러한 분류 방식이 기수 정렬의 기본적인 아이디어가 되었습니다.

기수 정렬은 초창기에는 펀치 카드와 같은 기계식 정렬 시스템에서 주로 사용되었지만, 컴퓨터가 발명되면서 디지털 데이터 정렬에도 적용되기 시작했습니다. 특히, 대량의 데이터를 효율적으로 정렬해야 하는 상황에서 기수 정렬은 그 진가를 발휘합니다.

2. 기수 정렬의 원리

기수 정렬은 각 자릿수(digit)를 기준으로 데이터를 정렬하는 과정을 반복합니다. 가장 낮은 자릿수(least significant digit, LSD)부터 시작하여, 가장 높은 자릿수(most significant digit, MSD)까지 차례대로 정렬을 수행합니다. 각 자릿수 정렬은 안정 정렬(stable sort) 알고리즘을 사용합니다. 안정 정렬이란, 정렬 과정에서 동일한 값을 가진 요소들의 상대적인 순서가 유지되는 정렬 알고리즘을 의미합니다.

1) LSD 방식

LSD(Least Significant Digit) 방식은 가장 낮은 자릿수부터 정렬을 시작합니다. 예를 들어, 10진수 정수를 정렬한다고 가정해 봅시다. 1의 자리, 10의 자리, 100의 자리 순으로 정렬을 수행합니다. 각 자리수 정렬은 버킷 정렬(bucket sort) 또는 계수 정렬(counting sort)과 같은 안정 정렬 알고리즘을 사용할 수 있습니다.

2) MSD 방식

MSD(Most Significant Digit) 방식은 가장 높은 자릿수부터 정렬을 시작합니다. 예를 들어, 10진수 정수를 정렬할 때, 100의 자리, 10의 자리, 1의 자리 순으로 정렬을 수행합니다. MSD 방식은 재귀적인 특성을 가지며, 각 자릿수 정렬 후, 동일한 값을 가진 요소들을 다시 정렬해야 합니다.

3) 기수 정렬 과정 예시

다음은 LSD 방식을 사용한 기수 정렬의 예시입니다. 정렬할 데이터는 다음과 같습니다:

170, 45, 75, 90, 802, 24, 2, 66

1. 1의 자리 정렬: 각 숫자의 1의 자릿수를 기준으로 버킷 정렬을 수행합니다.

   170, 90, 802, 2, 24, 45, 75, 66

2. 10의 자리 정렬: 각 숫자의 10의 자릿수를 기준으로 버킷 정렬을 수행합니다.

   2, 24, 45, 66, 170, 75, 90, 802

3. 100의 자리 정렬: 각 숫자의 100의 자릿수를 기준으로 버킷 정렬을 수행합니다.

   2, 24, 45, 66, 75, 90, 170, 802

위 과정을 거치면, 데이터가 정렬됩니다.

3. 기수 정렬의 구현

기수 정렬을 구현하는 방법은 여러 가지가 있지만, 가장 일반적인 방법은 LSD 방식을 사용하는 것입니다. LSD 방식의 기수 정렬은 다음과 같은 단계를 거칩니다.

1. 최대 자릿수 결정: 정렬할 데이터 중 가장 큰 숫자를 찾아, 그 숫자의 자릿수를 계산합니다.
2. 각 자릿수 정렬 반복: 최소 자릿수부터 최대 자릿수까지, 각 자릿수를 기준으로 안정 정렬을 수행합니다.

1) Python 코드 예시

다음은 Python으로 구현한 LSD 방식의 기수 정렬 코드입니다.

def counting_sort_for_radix(arr, exp):
    n = len(arr)
    output = [0] * n
    count = [0] * 10

    # Count the occurrences of digits at the current exponent
    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

    # Calculate cumulative counts
    for i in range(1, 10):
        count[i] += count[i - 1]

    # Build the output array
    i = n - 1
    while i >= 0:
        index = arr[i] // exp
        output[count[index % 10] - 1] = arr[i]
        count[index % 10] -= 1
        i -= 1

    # Copy the output array to the input array
    for i in range(n):
        arr[i] = output[i]


def radix_sort(arr):
    # Find the maximum number to know the number of digits
    max_num = max(arr)
    # Perform counting sort for every digit
    exp = 1
    while max_num // exp > 0:
        counting_sort_for_radix(arr, exp)
        exp *= 10

위 코드에서 counting_sort_for_radix 함수는 계수 정렬을 사용하여 각 자릿수를 정렬합니다. radix_sort 함수는 counting_sort_for_radix 함수를 호출하여 LSD 방식으로 기수 정렬을 수행합니다.

2) 코드 설명

• counting_sort_for_radix(arr, exp):
  • arr: 정렬할 배열
  • exp: 현재 자릿수 (1, 10, 100, ...)
  • 계수 정렬을 사용하여, arr 배열을 exp 자릿수를 기준으로 정렬합니다.
  • 안정 정렬을 위해, 배열의 순서를 유지합니다.
• radix_sort(arr):
  • arr: 정렬할 배열
  • max_num: 배열 내 최대값
  • exp: 현재 자릿수를 나타내는 변수
  • 최대 자릿수를 계산한 후, LSD 방식으로 각 자릿수를 기준으로 counting_sort_for_radix 함수를 호출하여 정렬합니다.

4. 기수 정렬의 시간 복잡도

기수 정렬의 시간 복잡도는 데이터의 크기($n$)와 자릿수의 개수($k$)에 따라 달라집니다. 각 자릿수 정렬에 사용되는 안정 정렬 알고리즘의 시간 복잡도가 $O(n+b)$라고 가정하면, 기수 정렬 전체의 시간 복잡도는 $O(k(n+b))$가 됩니다. 여기서 $b$는 각 자릿수의 가능한 값의 개수를 의미합니다. 예를 들어, 10진수 정수를 정렬하는 경우 $b=10$이 됩니다.

1) 일반적인 경우

일반적으로, 기수 정렬은 $O(kn)$의 시간 복잡도를 가집니다. 여기서 $k$는 데이터의 최대 자릿수입니다. 자릿수 $k$는 일반적으로 데이터의 크기 $n$에 따라 로그 함수 형태로 증가하므로, 기수 정렬은 데이터의 크기가 커져도 상대적으로 빠른 속도를 유지할 수 있습니다.

2) 최악의 경우

최악의 경우, 모든 데이터가 동일한 자릿수를 가질 때입니다. 이 경우에도 기수 정렬의 시간 복잡도는 $O(kn)$를 넘지 않습니다.

3) 공간 복잡도

기수 정렬의 공간 복잡도는 $O(n+b)$입니다. 이는 각 자릿수 정렬에 사용되는 버킷이나 계수 배열에 필요한 공간 때문입니다.

5. 기수 정렬의 장단점

1) 장점

• 빠른 속도: 비교 기반 정렬 알고리즘보다 빠른 속도로 정렬할 수 있습니다. 특히, 데이터의 크기가 크고 자릿수가 적은 경우에 효율적입니다.
• 안정성: 안정 정렬 알고리즘을 사용하므로, 동일한 값을 가진 요소들의 상대적인 순서를 보존합니다.
• 구현 용이성: 상대적으로 구현이 간단합니다.

2) 단점

• 데이터 타입 제한: 정수, 문자열 등 특정 데이터 타입에만 적용할 수 있습니다.
• 추가 공간 필요: 각 자릿수 정렬을 위해 추가적인 공간이 필요합니다.
• 자릿수 제한: 데이터의 자릿수가 너무 많으면, 성능이 저하될 수 있습니다.

6. 기수 정렬의 활용 사례

기수 정렬은 다양한 분야에서 활용됩니다.

• 데이터베이스 정렬: 데이터베이스 시스템에서 대량의 데이터를 정렬할 때 사용됩니다.
• 네트워크 라우팅: 네트워크 라우팅 테이블에서 IP 주소를 정렬하는 데 사용됩니다.
• 컴퓨터 그래픽스: 컴퓨터 그래픽스에서 픽셀 데이터를 정렬하는 데 사용됩니다.
• 통계 분석: 대규모 통계 데이터를 정렬하는 데 사용됩니다.

7. 주의사항 및 트러블슈팅

기수 정렬을 사용할 때 주의해야 할 몇 가지 사항이 있습니다.

1. 데이터 타입: 기수 정렬은 정수, 문자열 등 특정 데이터 타입에만 적용할 수 있습니다. 실수와 같은 다른 데이터 타입에는 사용할 수 없습니다.
2. 자릿수: 데이터의 자릿수가 너무 많으면, 각 자릿수 정렬에 필요한 시간이 증가하여 성능이 저하될 수 있습니다.
3. 메모리 사용량: 추가적인 공간을 사용하므로, 메모리 사용량에 유의해야 합니다. 데이터의 크기가 크고 메모리가 제한적인 환경에서는 다른 정렬 알고리즘을 고려해야 할 수 있습니다.
4. 안정 정렬: 기수 정렬은 각 자릿수 정렬에 안정 정렬 알고리즘을 사용해야 합니다. 불안정 정렬 알고리즘을 사용하면, 정렬 결과가 올바르지 않을 수 있습니다.

8. 결론

기수 정렬은 비교 기반 정렬 알고리즘의 한계를 극복하고, 특정 조건에서 빠른 정렬 속도를 제공하는 효율적인 알고리즘입니다. 데이터 타입, 자릿수, 메모리 사용량 등을 고려하여, 적절한 상황에서 기수 정렬을 활용하면 데이터 처리 성능을 향상시킬 수 있습니다. 기수 정렬은 복잡한 알고리즘은 아니지만, 데이터 정렬의 원리를 이해하고 효율적인 데이터 처리를 위한 중요한 도구입니다.