기수 정렬 (Radix Sort)

기수 정렬 (Radix Sort)

제한적인 범위 내에 있는 숫자(ex. 주민등록번호, 학번, 계좌번호)에 대해서 각 자릿수 별로 정렬하는 알고리즘

기(radix) : 특정 진수를 나타내는 숫자들

10진수의 기 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9

2진수의 기 : 0, 1

 

 

참고) 알기 쉬운 알고리즘

 

 

LSD 기수 정렬

Least Significant Digit(LSD) 기수 정렬

1의 자리부터 k자리로 정렬 수행

RL(Right-to-Left) 기수 정렬이라고도 함

MSD 기수 정렬

Most Significant Digit(MSD) 기수 정렬

k자리부터 1의 자리로 정렬 수행

LR(Left-to-Right) 기수 정렬이라고도 함

 

 

# LSD(RL) 기수 정렬
from collections import deque

def radix_sort_lsd(data, item_len):
    buckets = [deque() for _ in range(256)]     # 각 자릿수의 데이터를 담을 버켓 큐
    
    Q = deque(data)
    for idx in reversed(range(item_len)):
        while Q:
            # Q.popleft() : 항상 제일 왼쪽 요소가 리턴됨
            item = Q.popleft()
            # ord(문자) : 하나의 문자를 인자로 받고 해당 문자의 유니코드 정수를 반환
            # ord('a') = 97
            buckets[ord(item[idx])].append(item)
        
        for tbl in buckets: 
            while tbl:      
                Q.append(tbl.popleft())
            
        print(f'{idx}번째 문자\t ', end='')
        for item in Q:
            print(item, ' ', end='')
        print()


# 실행
if __name__ == "__main__":
    # 입력은 같은 길이의 문자열(ASCII) 배열
    a = ['lcfn', 'stgo', 'laax', 'frja', 'slin',
         'rtmf', 'ejff', 'ejwf', 'efef', 'ewwww']
    
    print('정렬 전:\t ', end='')
    for k in range(len(a)):
        print(a[k], ' ', end='')
    print()
    
    radix_sort_lsd(a, len(a[0]))

 

실행 결과