Colin's Blog
[파이썬] 기수 정렬 (Radix Sort)의 동작 방식

기수 정렬(Radix Sort)은 정렬 알고리즘 중 하나로, 자릿수를 기준으로 데이터를 정렬하는 방법입니다. 이 알고리즘은 숫자 데이터를 정렬하는 데에 주로 사용되며, 고급 정렬 알고리즘인 병합 정렬(Merge Sort)이나 퀵 정렬(Quick Sort)보다는 비교적 단순한 알고리즘이지만 특정한 상황에서 효과적으로 동작합니다.

동작 방식

기수 정렬은 자릿수를 기준으로 데이터를 정렬하는데, 각 자릿수를 기준으로 데이터를 비교하고 정렬합니다. 가장 낮은 자릿수부터 시작하여 가장 높은 자릿수까지 반복적으로 정렬을 수행합니다. 각 자릿수마다 정렬을 수행하는 기준을 기수(radix)라고 부릅니다.

예를 들어, 253, 982, 624, 109라는 숫자들을 정렬한다고 가정해봅시다. 기수 정렬은 가장 낮은 자릿수부터 비교하여 정렬합니다. 첫 번째로는 일의 자리에 있는 수를 기준으로 정렬합니다.

일의 자리에 있는 수를 기준으로 정렬한 결과는 위와 같습니다. 그 다음으로는 십의 자리에 있는 수를 기준으로 정렬합니다.

이렇게 하나의 자릿수를 기준으로 정렬하는 과정을 가장 높은 자릿수까지 반복하면 최종적으로 전체 데이터가 정렬되게 됩니다.

예시 코드

이제 파이썬을 사용하여 기수 정렬 알고리즘을 구현해보겠습니다. 다음은 입력으로 주어진 숫자 리스트를 기수 정렬하는 함수의 예시 코드입니다.

def radix_sort(arr):
    # 가장 큰 수의 자릿수를 구합니다.
    max_num = max(arr)
    max_digit = len(str(max_num))

    # 각 자리수를 기준으로 정렬을 수행합니다.
    for digit in range(max_digit):
        # 0부터 9까지의 숫자를 담을 임시 배열을 생성합니다.
        buckets = [[] for _ in range(10)]

        # 입력 배열의 숫자를 각 자리수에 맞는 버킷에 넣습니다.
        for num in arr:
            digit_val = (num // (10 ** digit)) % 10
            buckets[digit_val].append(num)

        # 버킷에 있는 숫자를 순서대로 꺼내고, 다시 입력 배열에 저장합니다.
        arr = [num for bucket in buckets for num in bucket]

    return arr

위의 코드에서는 입력으로 주어진 배열 arr에서 가장 큰 수의 자릿수를 구한 후, 각 자릿수를 기준으로 정렬을 반복적으로 수행합니다. 입력 배열을 순회하며 각 자릿수에 맞는 버킷에 숫자를 넣고, 버킷에 있는 숫자를 순서대로 꺼내어 다시 입력 배열에 저장합니다.

이제 다음과 같이 코드를 실행하여 기수 정렬을 테스트할 수 있습니다.

arr = [253, 982, 624, 109]
sorted_arr = radix_sort(arr)
print(sorted_arr)  # [109, 253, 624, 982]

결과는 [109, 253, 624, 982]가 되는 것을 확인할 수 있습니다.

기수 정렬은 비교적 단순한 알고리즘이지만, 데이터의 자릿수에 따라서 시간 복잡도가 영향을 받을 수 있습니다. 대체로 O(kn)의 시간 복잡도를 갖는데, 여기서 k는 가장 큰 수의 자릿수를 의미합니다. 따라서 입력 데이터가 매우 큰 범위의 수를 갖거나 자릿수가 균등하지 않을 경우에는 성능에 영향을 줄 수 있습니다.

© 2018 Colin. All rights reserved.