(분배그룹) / 기수정렬

기수정렬

기수는 숫자의 자릿수를 말한다. 예를 들어 10진수 숫자 42는 1의 자릿수가 2이고 10의 자릿수는 4인 정수이다.

기수 정렬은 키 값의 자릿수에 따라 자료를 분배하는 방식을 통해 정렬하는 알고리즘이다.

즉, 앞서의 정렬 알고리즘들이 각 자료의 키 값을 비교하여 이동을 수행하는 방식인 것과 비교하여

기수 정렬은 이러한 비교연산이 필요없으며 버킷이라 불리는 자료보관 큐에 자료를 분배하고 다시 이를 꺼내는 연산을 통해 정렬이 이루어진다.

예를들어 키 값이 10진수의 2자리 숫자라고 한다면, 먼저 1의 자리에 대해서 분배하고 각 버킷 벼롤 자료들을 꺼낸 다음 다시 10의 자리에 대해서

분배하고 버킷에서 자료들을 꺼내면 정렬이 완료된다.

입력데이터는 42, 60, 75, 81, 10, 23, 12, 18 이렇게 2자리 10진수 8개 정수다. 오름차순으로 간다.

정렬의 안정성도 유지된다는데..

우선 기수정렬의 특성은

자료의 키 값을 비교하는 연산이 필요없고 단순히 자료의 분배와 저장을 통해서만 정렬이 이루어진다.

따라서 기수 정렬은 자릿수가 d인 자료의 정렬이 경우 효율성은 O(d *n)이 되며,

실질적으로 효율성이 O(n)으로 볼 수 있다. 우수한 효율성이다..단...자릿수때문에 숫자 키의 경우에만 적용될 수 있다.

또한 자료의 분배 저장을 위한 버킷 메모리가 또 필요하다는 특성이 있다. 최선 평균 최악 : O(d * n)

(숫자에 대해서는 현존하는 알고리즘 중에서 가장 빠르다는데.. 자료 집합이 큰 경우 퀵 정렬보다도 빠르다)

배열은 속도는 빠르지만 메모리를 더 많이 차지하고 연결된 목록은 메모리 면에서 효율적이나 속도는 배열보다 느리다.

(자료가 적을땐 일반적으로 퀵 정렬이 더 낫다. 예를들어서 항목이 128개일때는 퀵 정렬이 기수 8 기수정렬보다 더 빠르다.

자료가 수천,수만을 넘어가야 기수 정렬이 퀵 보다 더 빠르게 된다)