기수 정렬(Radix sort) 알고리즘

오늘은 기수 정렬(Radix sort)에 대해 알아보겠습니다!

 

기수정렬은 지금까지 포스팅한 비교정렬 알고리즘(삽입, 선택, 퀵 등등)과는 다른 알고리즘인데욥

값을 일일이 비교하지 않고 정렬하는 알고리즘 입니다!

특히 이로인해 이론상 비교정렬의 하한 시간복잡도인 O(nlogn)을 뛰어넘는 정렬알고리즘입니다!

https://hipposdata.tistory.com/105

비교정렬 시간 성능의 하한(lower bound): O(nlogn)

 

# 동작과정 

# 기수정렬에서 기수(Radix)란 무엇일까요?

 

사전에서는 요로코롬 나와있는데요

 

 [숫자(數字)의 표현]  숫자 표현(진법체계)에 기준이 되는 수
     - 例) radix-2 : 2진 {0,1}, radix-10 : 십진 {0,1,...,9} 

 

 ( [정보통신기술용어해설] http://www.ktword.co.kr/test/view/view.php?no=4360 )

 

 

즉, 각 자리수를 기준으로 정렬하는데 사용되는 수로 숫자나 문자의 자리수마다 사용할 수 있는 값의 범위를 나타낸다고 할 수 있습니다!

 

예를 들어,

10진수 숫자의 각 자리수는 0부터 9이므로 기수(radix)는 10

2진수 숫자는 0,1 이므로 기수(radix)는 2

알파벳은 A~Z 까지 총 26개이므로  기수(radix)는 26

 

# 그렇다면 기수정렬(Radix sort)은 무엇일까요?

기수정렬은 기수(Radix) 의미에서도 알 수 있듯이 숫자나 문자열을 자리수별로 나누어 낮은 자리수부터 순차적으로 정렬하는 방식으로 

자릿수를 기준으로 정렬하는 방식입니다!

170, 75, 45, 92, 3, 24 총 6개의 수를 오름차순으로 정렬해보겠습니다!

각각 1, 10, 100의 자리를 기준으로 순차적으로 정렬해나가면 됩니다 

 

# Python 코드

10진수이므로 0~9까지 10개의 수를 구분할 수 있는 BUCKETS(버킷)과 처리할 자리수인 DIGITS(최대 자리수)를 입력하여 구현하면 됩니다!

특히  BUCKETS(버킷)은 큐(Queue)를 이용하여 FIFO(first in first out)의 특성을 활용한다면 쉽게 구현할 수 있습니다

from queue import Queue

BUCKETS = 10 # 10진수(0~ 9)

DIGITS = 3 # 최대 자리수 입력

def radix_sort(A):

    queues = []  # 큐의 리스트

    for i in range(BUCKETS):

        queues.append(Queue())  # BUCKETS개의 큐 사용

    n = len(A)

    factor = 1  # 1의 자리부터 시작

    for d in range(DIGITS):  # 모든 자리에 대해

        for i in range(n):  # 자릿수에 따라 큐에 삽입

            queues[(A[i] // factor) % 10].put(A[i])  # 숫자 삽입

        i = 0

        for b in range(BUCKETS):  # 버킷에서 꺼내어 원래의 리스트로

            while not queues[b].empty():  # b번째 큐가 비어있지 않는 동안

                A[i] = queues[b].get()  # 원소를 꺼내 리스트에 저장

                i += 1

        factor *= 10  # 그 다음 자리로

    return A

 

 

# 성능분석 - 시간복잡도

기수정렬의 시간복잡도는 다른 비교정렬에 비해 매우 빠르게 동작하는데욥

최대 자리수와 각 자리수의 개수만큼 곱하면 총 시간복잡도를 구할 수 있습니다.

 

(최대 자릿수 d) X (각자리의 구분되는 수 n (버킷수 => 10진수는 10, 2진수는 2, 알파벳은 26))

= O(nd)

 

하지만 여러 단점이 있는데욥

구현시 최대 자릿수를 미리 알아야하고

최대 자릿수d가 큰 데이터에서는 실제 O(nlogn)의 비교정렬보다 더 느려질 수 있으며

추가적인 버킷(큐)을 사용하여 자릿수마다 데이터를 저장하므로 메모리를 많이 사용

 

# 관련 문제

백준 10989번 수 정렬하기 3 

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

 

# reference

파이썬 자료구조와 알고리즘: for beginner. (2021). 대한민국: 한빛아카데미.

Do it! 알고리즘 코딩 테스트 - 파이썬 편(김종관 저/이지스퍼블리싱 (주))