정렬 알고리즘 - 기수정렬(radix sorting) - 파이썬(python)

계수정렬(counting sort)를 이용한 기수 별로 비교없이 수행하는 정렬 알고리즘.

 

비교연산을 하지 않아서 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블만한 메모리가 더 필요하다.

 

가장 작은 자리수부터 비교하는 방법을 LSD(Least-Significant-Digit)라고 하고.

가장 큰 자리수부터 비교하는 방법은 MSD(Most-Significant-Digit)라고 한다.

 

LSD예시

 

lists=[127, 564, 3218, 89, 524, 6, 72, 103, 1216]

 

 

먼저 1의 자리 비교

 

각각 1의자리는 7 4 8 9 4 6 2 3 6 이므로

 

[72], [103], [564, 524], [6, 1216], [127], [3218], [89] 이다.

 

동일한 방법으로 10의자리를 기준으로 정렬하면 (한자리수의 경우 10의자리는 0으로 본다)

 

[6,103],[1216,3218],[524,127],[564],[72],[89]

 

100의자리 기준

 

[6,72,89],[103,127],[1216,3218],[524,564]

 

1000의자리 기준

 

0,0,0,0,0,1,3,0,0 이므로

 

[6,72,89,103,127,524,564,1216,3218]

 

정렬 끝!

 

 

파이썬 코드

import sys

# ex) get_i_th_digit("3612",0)-->2
#     get_i_th_digit("3612",2)-->6

def get_i_th_digit(num,index): # num-> type(str)
    if len(num)<=index:
        return 0
    result=int(num[len(num)-index-1])
    return result

def count_sort(data,index): # data -> str type num list
    n=len(data)

    # decimal num is 0~9
    table=[0]*10

    # counting each element
    for element in data:
        table[get_i_th_digit(element,index)]+=1
        
    # compute location each element(prefix sum)
    s=0
    for k in range(len(table)):
        s+=table[k]
        table[k]=s

    # for j in range(1,len(table)):
    #     table[j]+=table[j-1]
    
    sorted_arr=[0]*n
    
    for ele in reversed(data):
        di=get_i_th_digit(ele,index)
        sorted_arr[table[di]-1]=ele
        table[di]-=1
    
    return sorted_arr


def radix_sort(lists):
    # convert list num to str
    str_lists=[]

    for i in lists:
        str_lists.append(str(i))

    max_len=max([len(s) for s in str_lists])
    

    for j in range(max_len):
        str_lists=count_sort(str_lists,j)
    
    # re-convert str to int
    # for k in range(len(str_lists)):
    #     str_lists[k]=int(str_lists[k])

    return str_lists
    

lists=[127, 564, 3218, 89, 524, 6, 72, 103, 1216]
print(radix_sort(lists))

 

정렬 결과