[Algorithm] [Sort] Radix Sort ( 기수 정렬 )

 

오늘은 Radix sort 에 대해서 알아보려고 한다.

 

 

 

Radix sort란?

 

낮은 자리 수부터 정렬하여 숫자들을 빠르게 정렬할 수 있는 sort 방식이다.

 

 

장점

 

◎ Stable sort

◎ θ(n) 까지 가능

◎ LSD sort

 

---

 

 

배경 지식

 

LSD , MSD

 

LSD : Least Significant Digit 의 약자로 낮은 자릿수를 뜻한다.

MSD : Most Significant Digit 의 약자로 높은 자릿수를 뜻한다.

 

52,314 를 예로 들면

가장 중요한 숫자는 10,000의 자리에 있는 5 이다.

그리고 가장 덜 중요한 숫자는 1의 자리에 있는 4이다.

 

즉 , LSD sort는 낮은 자리 부터 정렬을 하겠다는 것이고,

MSD sort는 높은 자리 부터 정렬을 하겠다는 것이다.

 

Radix sort는 LSD sort 방식이다.

 

진행 방식

 

RadixSort(Array , digits): 				//digits 는 자릿수
	for i = 1 to digits
    	Stable Sort(A) on digit i

 

 

Radix sort는 각 자리 마다 Stable sort를 진행 해준다.

Stable sort로 어떤 sort algorithm을 사용하느냐가 시간 복잡도를 결정한다.

 

Stable sort에는 Insertion sort, Selection sort , Counting sort 등등 이 있는데

Counting sort가 가장 빠르기 때문에 Counting sort가 적합하다.

 

 

 

 

Counting sort를 잘 모르겠다면 아래 포스터를 참조하자

 

 

2022.05.27 - [Algorithm_Analysis] - [Algorithm][Sort] Counting sort( 계수 정렬 ) 총 정리 및 예제

[Algorithm][Sort] Counting sort( 계수 정렬 ) 총 정리 및 예제

 

 

시간 복잡도 계산

 

 

Counting sort의 시간복잡도 : Θ(n+k)

자릿수 : d

 

 

Counting sort를 이용한 Radix sort의 시간복잡도 계산 : Θ( d * (n+k) )

 

d는 상수 , k는 O(n)이므로

 

결국 Θ(n)