[정렬] 7. 한 살도 이해하는 기수 정렬(radix sort)

기수 정렬

: 주어진 수 들간의 비교를 하지 않고 버킷을 사용해 정렬하는  방법으로,

낮은 자리(1의 자리)에서 높은 자리(10^n 자리) 순으로 버킷에 넣는 방법으로 정렬한다.

 

실제로 숫자들 간의 비교를 통해 정렬을 하는 것이 아닌, 0~9까지의 버킷이 있고 이 버킷에 숫자를 넣어가며 분류한다고 생각하면 된다.

 

시간복잡도

O(r*n) : r은 숫자의 자릿수, n은 정렬될 수의 갯수

 

특징

1.  시간 복잡도에서 엄청난 이점을 갖는다. 무려 O(N)..

2. 하지만 그만큼 추가적인 메모리가 많이 필요하다.

 

 

[153, 262, 37, 598, 433, 855]를 기수 정렬을 이용해 정렬해보자.

가장 낮은 1번째 자리부터(1의 자리) 가장 높은 3번째 자리(100의 자리) 순으로 정렬한다.

다음과 같이 0~9 까지 버킷들이 자릿수 별로 있고, 해당하는 자릿수에 맞게 버킷에 담게된다.

                    1의 자리 정렬                                              10의 자리 정렬                                                    100의 자리 정렬

 

결과적으로 [37, 153, 262, 433, 598, 855] 로 정렬되는 모습을 볼 수 있다.

 

영상을 참고해서 이해하면 이제 완벽히 이해가 갈 것이다.

 

 

기수정렬

영상을 설명하자면,

1의 자리 버킷에 수들을 담고 -> 버킷에 담긴 순서대로 꺼내온다. (1의 자리로 정렬)

이 꺼내온 것을 이번엔 10의 자리 버킷에 수들을 담고 -> 버킷에 담긴 순서대로 꺼내온다. (10의 자리로 정렬)

이 꺼내온 것을 마지막으로 100의 자리 버킷에 수들을 담고 -> 버킷에 담긴 순서대로 꺼내온다. (100의 자리로 정렬)

 

기수 정렬 Python 코드를 살펴보자.

from collections import deque

def radixSort():
    nums = list(map(int, input().split(' ')))
    buckets = [deque() for _ in range(10)]
    
    max_val = max(nums)
    queue = deque(nums)
    digit = 1 # 자릿수
    
    while (max_val >= digit): # 가장 큰 수의 자릿수일 때 까지만 실행
        while queue:
            num = queue.popleft()
            buckets[(num // digit) % 10].append(num) # 각 자리의 수(0~9)에 따라 버킷에 num을 넣는다.
        
        # 해당 자릿수에서 버킷에 다 넣었으면, 버킷에 담겨있는 순서대로 꺼내와 정렬한다.
        for bucket in buckets:
            while bucket:
                queue.append(bucket.popleft())
        print(digit,"의 자릿 수 정렬: ", list(queue))
        digit *= 10 # 자릿수 증가시키기
    
    print(list(queue))

 

입력과 출력