[Algorithm] Radix Sort (기수 정렬)

0. Radix Sort (기수 정렬) 이란?

 

기수 정렬이란, 맨 뒤에 있는 자릿수부터 해당 자릿수를 기준으로 정렬한 뒤, 한 칸씩 (한 자리씩) 앞으로 이동하며 각 자리수를 기준으로 정렬하다가 최종적으로 가장 높은 자리수를 기준으로 정렬하는 방법이다. 

 

숫자들 간의 자릿수가 다르다면 어떻게 할까? 자릿수가 작은 수의 앞을 0으로 채우면 반드시 작아지게 된다. (ex. 100, 99의 경우 100과 099를 비교하면 마지막에는 가장 높은 자리수와 비교하므로 1과 0이 비교되어 100이 더 크다고 판별된다).

 

음수가 섞여 있는 경우에는 음수랑 양수를 구분하여 정렬한 후 합치면 된다. 이 때 음수는 절댓값으로 변환하여 비교한 뒤 reverse해주면 정렬된 값을 얻을 수 있다. (ex. -3, -40, -12 > 3 12 40 > -40 -12 -3)

 

1. 구현

 

구현은 codetree 문제에서 주어진 대로 1과 100000 사이의 자연수가 들어온다고 가정하였다. 

 

n = int(input())
nums = input()
num = nums.split()
max_digit = 0
max = 0

for i in range(n):
    if(len(num[i]) > max_digit):
        max_digit = len(num[i])

for i in range(n):
    if(len(num[i])<max_digit):
        for j in range(max_digit-len(num[i])):
            num[i] = '0' + num[i]

for i in range(max_digit-1, -1, -1):
    num_next = []
    dict_digit = {}
    for tmp in range(10):
        dict_digit[tmp] = []
    for j in range(n):
        tmp_num = num[j]
        dict_digit[int(tmp_num[i])].append(tmp_num)
    for key in dict_digit:
        for k in range(len(dict_digit[key])):
            num_next.append(dict_digit[key][k])
    num = num_next

for i in range(n):
    print(num[i], end=' ')

python의 dictionary 기능을 사용했다.

모든 숫자의 자릿수를 맞추어주기 위해 string 형태로 input 값을 유지하여 자릿수가 작은 숫자는 앞에 0을 붙여주었다.

이후 맨 뒤 자릿수부터 해당하는 자릿수의 숫자를 dictionary 형태로 넣어주었다. (ex. 108을 둘째 자리에서 비교할 때, 0이라는 key의 value로 저장된다). 이를 이용하여 정렬하고, 정렬된 배열을 다음 for문의 첫 배열로 넣어준다.