Radix Sort란?

데이터의 각 자릿수를 낮은 자리에서부터 가장 큰 자리수까지 순차적으로 올라가면서 정렬을 하는 것

Radix Sort의 특징

1) 비교연산을 수행하지 않는 정렬 ---> 속도가 빠른 정렬
2) 버킷이라는 추가 메모리를 요구한다. ---> 기수(radix)만큼의 메모리 공간 추가 필요
	Problem: 길이가 다른 데이터의 정렬

TimeComplexity & Stability

데이터들의 자릿수(digit)를 d라 하고, 데이터의 개수를 N이라 하자
추가 메모리 요구량: $d$
1) $1$의 자릿수부터 버킷에 넣으면서 정렬 ---> $O(n)$만큼 걸림
2) $1$의 과정을 $d$번째 자릿수까지 진행 ---> $d \times O(n)$

Implementation

코드를 입력하세요