[자료구조] Radix Sort (기수 정렬)

개념

낮은 자릿수(혹은 높은 자릿수)부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘

정렬 속도가 빠름
문자열, 정수 정렬이 가능(자리수를 비교해서 정렬하는 방식)
안정 정렬
비교연산이 없음

자릿수가 없는 경우 정렬 불가
데이터 전체 크기에 기수 테이블의 크기만한 메모리가 필요

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

MSD(Most-Significant-Digit) : 가장 큰 자리수부터 비교하는 방법

 

https://soobarkbar.tistory.com/156?category=848286

 

1. 1의 자리를 비교하여 1의 자리를 기준으로 정렬
2. 10의 자리를 비교하여 10의 자리를 기준으로 정렬
3. 100의 자리를 비교하여 100의 자리를 기준으로 정렬
...


시간복잡도

정렬하는 숫자의 자릿수에 따라 시간복잡도 O(dn)을 가짐
d = 정렬할 숫자의 자릿수