/ PROGRAMING, PYTHON

기수정렬

기수정렬(Radix Sort)

기수정렬은 정렬 알고리즘의 하나로, 비교 기반 정렬 알고리즘과 달리 자리값을 기준으로 정렬하는 방식입니다.

주로 정수, 문자열을 정렬하는데 사용됩니다.

일반적으로 LSD(Least Significant Digit)와 MSD(Most Significant Digit)로 분류됩니다.
LSD 기수정렬은 가장 낮은 자리수부터 시작하여 정렬하는 것입니다.
MSD 기수정렬은 가장 높은 자리수부터 시작하여 정렬하는 것입니다.

안정 정렬(Stable Sort)이기 때문에 같은 값이 있을 경우에도 원래의 상대적인 위치가 유지됩니다.
또한, 시간 복잡도는 O(d * (n + k))입니다.
여기서 d는 정렬할 자리수, n은 정렬할 숫자의 개수, k는 사용하는 기수(진법)의 크기를 나타냅니다.

데이터의 자리수를 기준으로 비교하고 정렬하기 때문에 데이터의 길이가 짧을수록 정렬의 시간이 짧아집니다.
비교 데이터의 자리수가 모두 동일해야합니다.

예를 들어, 정수형 데이터를 LSD 기수정렬 해보겠습니다.
10, 21, 33, 45, 51, 62, 78, 83, 92 를 기수정렬로 정렬해보겠습니다.

일의 자리부터 비교하여 정렬합니다. 10, 21, 51, 62, 92, 33, 83, 45, 78

십의 자리를 비교하여 정렬합니다. 10, 21, 33, 45, 51, 62, 78, 83, 92

추천 사이트 위키독스 기수정렬 네이버 블로그 - 자료구조 기수정렬

LSD 예시1

장점 : 코드를 보고 이해하기 쉽습니다.
단점 : 메모리 효율이 좋지 않습니다.

def radix_sort_lsd(arr):
    # 입력된 리스트에서 최대값을 찾습니다.
    max_val = max(arr)
    
    # 각 자리수를 기준으로 정렬합니다.
    digit = 1
    while max_val // digit > 0:
        arr = radix_sort_lsd_helper(arr, digit)
        digit *= 10 # digit의 자리수를 늘려가며 비교합니다.
        
    return arr

# 주어진 배열의 특정 자리수의 정렬을 합니다.
def radix_sort_lsd_helper(arr, digit):
    # 배열을 담을 수 있는 배열을 생성합니다.
    bucket_list = [[] for _ in range(10)] # 0~9, 10개만 가능합니다.
    
    for i in arr:
        Index_arr = i // digit
        Index_arr = Index_arr % 10
        bucket_list[Index_arr].append(i)
        
    arr = []
    for bucket in bucket_list:
        arr += bucket
        
    return arr


arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort_lsd(arr)
print(sorted_arr)

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

LSD 예시2

장점 : 메모리 효율이 좋습니다.
단점 : 코드를 이해하기 어렵습니다.

누적합을 이용해서 인덱스 위치를 찾아 정렬해줍니다.

def radix_sort_lsd(arr):
    # 입력된 리스트에서 최대값을 찾습니다.
    max_val = max(arr)

    # 각 자리수를 기준으로 정렬합니다.
    digit = 1
    while max_val // digit > 0:
        arr = radix_sort_lsd_helper(arr, digit)
        digit *= 10

    return arr

def radix_sort_lsd_helper(arr, digit):
    # 각 자리수를 기준으로 숫자를 세어 정렬합니다.
    count_list = [0] * 10
    for val in arr:
        idx = (val // digit) % 10
        count_list[idx] += 1
        
    # 누적합 리스트를 구합니다.
    for i in range(1, len(count_list)):
        count_list[i] += count_list[i-1]

    # 버킷 리스트를 구합니다.
    bucket_list = [0] * len(arr)
    for val in reversed(arr):
        idx = (val // digit) % 10
        count_list[idx] -= 1
        bucket_list[count_list[idx]] = val

    return bucket_list

arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort_lsd(arr)
print(sorted_arr)

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