sort1 Radix Sort Radix sort 키값에 대한 속성이 주어졌을 때, 비교 연산이 아닌 다른 연산을 사용해 linear time에 정렬을 수행할 수 있다. 속성 예시 : 이름, 다섯 자리 10진수, 범위가 정해진 정수 정렬 과정 1. 서로 다른 pile에 분배 - θ(n) 2. 각각의 pile을 정렬 3. 정렬된 pile들을 합침 - θ(n) 최하위 숫자(or 비트, 문자, 필드)순으로 pile에 분배하면 정렬 과정을 생략 가능 Total O(d*(n+k)) (d: 필드 수(ex. 다섯 자리 십진수에서 5), k: pile 수(ex. 다섯 자리 십진수에서 10(0~9))) -> d, k가 constant라면 θ(n) 2021. 4. 9. 이전 1 다음