[알고리즘] 기수정렬(radix sort)

🚩 기수정렬?

기수 정렬은 전체 값을 비교하지 않는 특이한 정렬로, 두 값을 놓고 비교할 때
자릿수에 있는 데이터를 비교한다.

기수정렬의 시간복잡도는 O(kn)인데, 여기서 k는 데이터의 자릿수를 말한다. 즉, 데이터의 자릿수가 많지 않으면서 데이터 수는 많을 경우 기수정렬을 활용하는 것이 효과적이라고 할 수 있다.

기수정렬의 핵심 이론

기수정렬은 10개의 큐를 이용한다. 여기서 각 큐는 자릿수를 대표하는데, 각 자릿수가 0~9까지 10개이기 때문에 10개의 큐를 이용하는 것이다.

다음과 같은 데이터가 있다고 하자.

[16 80 18 77 03 24 80 23]
일의 자릿수를 기준으로 데이터를 큐에 저장했을 때 다음과 같다.
[80][23, 03][24][16][77][88, 18]

1의 자리를 기준으로 해당 데이터들은 정렬되어있는 것을 알 수 있다. 이제 일의 자릿수가 정렬된 데이터들을 가지고, 10의 자리를 기준으로 큐에 저장해보자.

[03][16,18][23, 24][77][80 88] -> 순서대로 나열하면 03 16 18 23 24 77 80 88

보시다시피 숫자가 모두 정렬되어있는 것을 알 수 있다. 이 정렬에서의 핵심은, 앞서 작은 자릿수에서 정렬된 데이터의 순서를 그대로 가지고와서 다시 다음 자릿수의 정렬에 활용한다는 것이다. 그렇게 되면 데이터들이 비교한 자릿수까지는 모두 정렬된 상태가 되는 것이다.

또한 위 경우에는 자릿수가 10의자리까지 갖는 데이터들을 정렬했기 때문에 데이터를 2*N번 탐색하게 되었는데, 이때 2N의 시간복잡도를 가지게 되는 것을 알 수 있다.

이론 정리

기수정렬은 시간복잡도가 짧은 축에 속하는 편이다. 그렇기 때문에 데이터의 수가 많고, 자릿수가 적은 데이터들을 다뤄야 할 경우, 활용도가 높은 알고리즘이라고 할 수 있다.

💾 코드

from collections import deque

data = [437,123,234,578,351,625,543,30,7,12,199] # 예시 데이터

def radix(arr): # x - 자릿수
    buckets = [deque() for _ in range(10)]
    N = 1
    max_num = max(arr)
    Q = deque(arr)
    while N <= max_num:
        while Q:
            num = Q.popleft()
            buckets[(num//N)%10].append(num) # 자릿수대로 큐에 저장

        for bucket in buckets: # 순서대로 다시 배열에 저장
            while bucket:
                Q.append(bucket.popleft())

        N *= 10 # 다음 자릿수 비교를 위해 N에 10 곱하기
    return list(Q)

print(radix(data))