[ 기수 정렬 ] 알고리즘

 

 

1.  개념

      

       기수 정렬 : 기수 정렬은 숫자의 특정 자릿수만 비교하는 정렬인데 일의 자릿수부터 차례대로 하나씩 비교한다

 

 

        * 시간 복잡도 : O(kn)

 

         

          기수 정렬 방법

       

          1 ) 0 ~ 9를 상징하는 10개의 큐를 사용한다

 

          2 ) 데이터를 특정 자릿수의 숫자를 기준으로 큐에 넣는다

 

         3 ) 일의 자릿수부터 마지막 자릿수까지 차례대로 반복하면 된다

 

 

 

2.  문제 풀이

 

# 1  수 정렬하기 - 백준 10989번

https://www.acmicpc.net/problem/10989

10989번: 수 정렬하기 3

 

from collections import deque
N = int(input())
num = []

for i in range(N):
    num.append(int(input()))

def radixSort(nums):
    # 0~9 버킷(큐)
    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)
        
        # 버킷에 담겨있는 순서대로 꺼내기
        for bucket in buckets:
            while bucket:
                queue.append(bucket.popleft())
        
        digit *= 10 # 자릿수 증가시키기
    
    return queue

numList = radixSort(num)
for i in range(N):
    print(numList[i])

 

 

 

 

 

 

 

!참고!

https://10000cow.tistory.com/entry/정렬-7-기수-정렬radix-sort

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