기수 정렬(radix sort)에 대한 설명으로 옳은 것만을 모두 고르… | [7급 국가직 알고리즘] 26년 1회차 기출문제 상세 페이지

기수 정렬에 대한 옳은 설명은 추가 저장공간이 필요하다는 것과 안정적 정렬이라는 것이다.
기수 정렬은 키를 자릿수별로 나누어 각 자릿수에 대해 버킷(또는 계수 정렬)으로 분배하는 방식이며, 하위 자릿수 결과를 보존하려면 각 단계의 정렬이 안정적이어야 한다.
원소끼리 크기를 비교하지 않고 자릿수 값으로 분배하므로 비교 기반 정렬이 아니다.
자릿수가 d, 기수가 k이면 시간 복잡도는 $O(d(n+k))$로, 비교 정렬의 하한인 $O(n\log n)$이 아니라 선형 시간에 가깝다.