에듀윌
·
기수 정렬
기수 정렬
RADIX SORT
자릿수로 분류 —
비교 안 하는
유일한 정렬
핵심
숫자의
자릿수
를 보고 0~9 버킷에 분배만 함. 두 값을
서로 비교하지 않음
. 자릿수 d일 때
O(dn)
.
초기
123·45·678·9
→
1의 자리
버킷 분배
→
10의 자리
버킷 분배
→
100의 자리
버킷 분배
→
정렬 완료
시험 한 줄
'
비교를 하지 않는 정렬
' 또는 '
자릿수 기반 정렬
' 키워드 보이면 기수 정렬 즉답. 우편번호 분류와 같은 원리.