[자료구조]기수 정렬(radix sort)....

기수정렬 기수정렬 기수정렬 기수정렬 기수정렬 기수정렬 기수정렬

기수 정렬은 분배 방식의 정렬 방법으로 정렬할 원소의 키값에 해당하는 버킷에 원소를 분배하였다가 버킷의 순서대로 원소를 꺼내는 방법을 반복한다. 기수 정렬은 원소의 키를 표현하는 값의 기수만큼의 버킷이 필요하고, 키값의 자릿수만큼 기수 정렬을 반복한다. 10진수로 표현된 키값을 가진 원소들을 정렬할 때는 0부터 9까지 10개의 버킷을 사용한다. 

 먼저 키값의 일의 자리에 대해서 기수 정렬을 수행하고, 다음 단계에서는 키값의 십의 자리에 대해 그리고 그 다음 단계에서는 백의 자리에 대해서 기수 정렬을 수행한다. 한 단계가 끝날 때마다 버킷에 분배된 원소들을 버킷의 순서대로 꺼내서 다음 단계의 기수 정렬을 수행해야 하므로 큐를 사용하여 버킷을 만든다.

기수 정렬의 수행 시간은 정렬할 원소의 수 n과 키값의 자릿수 d와 버킷의 수를 결정하는 기수 r에 따라 달라진다. 정렬할 원소 n개를 r개의 버킷에 분배하는 작업이 n+r이고, 이 작업을 자릿수 d만큼 반복해야 하므로 수행할 작업은 d(n+r)이 된다. 따라서 시간복잡도는 O(d(n+r))이 된다.

기수정렬 기수정렬 기수정렬 기수정렬 기수정렬 기수정렬 기수정렬