알고리즘

기수 정렬

■ 기수 정렬 분석

기수 정렬을 d 자리수 숫자들에 대하여 계수 정렬로 정렬한다면 각 자리에 대하여 O(n)시간이 걸리므로 전체로는 O(dn) 시간이 걸리는데 d를 상수로 취급할 수 있다면 기수 정렬은 O(n) 시간이 걸림
구체적인 예로 약 백만개(=2²⁰) 정도의 64비트 수치를 정렬한다고 하자. 이 수치를 2¹⁶진법의 4자리수로 간주한다면 계수 정렬을 단지 4번만 반복하면 정렬을 끝낼 수 있음
⇒64비트 수=2⁶⁴=2^16*4 이런 수가 백만(2²⁰)개가 있을 때임
이를 O(nlogn)시간의 비교 기반 정렬 알고리즘으로 정렬한다면 개략적으로 숫자당 logn=20번의 연산이 필요할 것이므로 기수 정렬이 훨씬 빠름
기수 정렬은 각 자리수를 정렬할 때 계수 정렬을 이용했는데 이 계수 정렬은 정렬과정에서 전체 정렬 데이터 개수 만큼의 메모리와 진법 크기 만큼의 메모리가 추가로 필요한 비제자리 정렬이므로 메모리의 여유가 많지 않을 경우에는 실제로 적용하기 어려운 정렬 방법