[java] 파이썬에서 기수 정렬 구현하기

15 Dec 2023

java

기수 정렬(Radix Sort)은 비교를 사용하지 않고 정수를 정렬하는 안정적인 정렬 알고리즘입니다. 이 알고리즘은 각 키를 정렬하기 위해 키의 자릿수를 기준으로 정렬하는 방식을 사용합니다. 파이썬에서 기수 정렬을 구현하는 방법에 대해 알아보겠습니다.

기수 정렬 알고리즘

파이썬에서 기수 정렬을 구현하는 가장 일반적인 방법은 다음과 같습니다.

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

    for i in range(n):
        index = arr[i] // exp
        count[index % 10] += 1

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

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

    for i in range(n):
        arr[i] = output[i]

def radix_sort(arr):
    max_num = max(arr)
    exp = 1
    while max_num // exp > 0:
        counting_sort(arr, exp)
        exp *= 10

예시

다음은 기수 정렬 알고리즘을 사용하여 배열을 정렬하는 예시입니다.

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

결론

이렇게 파이썬에서 기수 정렬을 구현할 수 있습니다. 기수 정렬은 키의 자릿수를 기준으로 정렬하기 때문에 정확하고 효율적인 정렬 방법으로 널리 사용되고 있습니다.