기수 정렬(Radix Sort)의 원리와 시간 복잡도의 함정

• •자릿수별 버킷 배치 방식
• •LSD(Least Significant Digit) 정렬 과정
• •비교 연산이 없는 정렬 메커니즘

기수 정렬은 안정 정렬(Stable Sort)의 특성을 활용하여 이전 자릿수의 정렬 상태를 보존한다.

• •시간 복잡도 O(nd)의 정의
• •자릿수(d) 증가에 따른 성능 저하
• •O(n log n) 알고리즘과의 효율성 역전 현상

Big-O 표기법에서 상수로 취급되던 자릿수가 실제 성능에서는 결정적인 변수가 된다.

• •데이터 범위가 제한된 대규모 데이터셋에 최적
• •자릿수 고정 시 O(n) 성능 발휘
• •데이터 특성에 따른 알고리즘 선택 기준

데이터의 분포와 범위를 미리 알고 있을 때 최적의 알고리즘 선택이 가능하다.