기수 정렬(Radix Sort)

🟩 자리수를 비교하며 정렬을 진행하는 알고리즘

 

🟩 종류

1. LSD (Least Significant Digit) 기수 정렬

가장 작은 자릿수부터 정렬 진행 (예 : 일의 자릿수부터)

Right-to-Left

가장 작은 자릿수부터 큰 자릿수까지 비교해야 한다는 단점이 있지만, 코드 구현이 MSD에 비해 간결하다.

마지막 자릿수까지 검사를 마친 경우, 오름차순으로 정렬이 완료됨

 

2. MSD (Most Significant Digit) 기수 정렬

가장 큰 자릿수부터 정렬 진행

Left-to-Right

LSD와 비교했을 때, 정렬 상태 확인 등의 추가 작업이 필요하지만, 중간에 정렬이 완료될 수 있다는 장점이 있다.

 

 

🟩 특징 및 장단점

정렬 순서상 앞과 뒤의 판단을 위한 비교 연산을 하지 않음

정렬 대상의 모든 길이가 동일해야 가장 효율적

정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐' 방식(FIFO)으로 저장 후 다시 꺼낸다.

 

(장) 키의 길이 d가 작다면 O(n)의 시간으로 정렬이 가능하기 때문에 굉장히 빠른 속도로 정렬 가능

(장) 비교 연산 없이 정렬 수행 가능

(단) 추가적으로 버킷을 사용하기 때문에 데이터 크기에 비례한 메모리 필요

(단) 정렬의 특수성 때문에, 부동소수점 및 실수 등 특수한 비교 연산이 필요한 데이터에는 적용이 어렵다.

 

🟩 시간복잡도 O(n)

키의 수를 n, 키의 최대 길이를 d라 할 때 O(d * n)