기수 정렬 (Radix Sort)
1. 개념 설명
(1) 기수 정렬은 간단하게 말하면 데이터의 N진법을 기준으로 정렬하는 알고리즘이다.
( 예를 들면, N이 10이고 정렬할 데이터는 10, 5, 15, 234, 1이라고 하자. 그렇다면 아래와 같이 기준을 잡는다. )
10^0의 자리: 0) 010, 1) 001, 4) 234, 5) 005, 015. 순서대로 이어붙이면 010, 001, 234, 005, 015.
10^1의 자리: 0) 001, 005, 1) 010, 015, 3) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.
10^2의 자리: 0) 001, 005, 010, 015, 2) 234. 순서대로 이어붙이면 001, 005, 010, 015, 234.
( 이 과정을 거치면 정렬된 결과인 1, 5, 10, 15, 234가 나오게 된다. )
(2) 기수 정렬은 계수 정렬의 비효율성을 개선하기 위해서 사용할 수 있다.
2. 과정
- 실제로 수행되는 과정이며, 기수 정렬 알고리즘 중 *LSD를 시각화한 것이다.
( 기수 정렬의 방식으로 LSD와 MSD가 있다. )
( LSD는 Least Significant Digit의 약자로 가장 작은 자릿수부터 정렬을 진행해 나가는 방식을 말한다. )
( MSD는 Most Significant Digit의 약자로 가장 큰 자릿수부터 정렬을 진행해 나가는 방식을 말한다. )
( EX) a와 ab 사전순으로 정렬할 때 )
3. 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
|
public class RadixSort {
private static int[] A = { 38, 27, 43, 9, 3, 82, 10 };
private static final int BUCKET_SIZE=10; //자릿수는 0~9까지가 최대이므로, bucket 사이즈는 10
public static void main(String[] args) {
System.out.println("정렬 전: " + Arrays.toString(A));
radixSort(A.length);
System.out.println("정렬 후: " + Arrays.toString(A));
}
public static void radixSort(int len) {
Queue<Integer>[] bucket = new LinkedList[BUCKET_SIZE];
for(int i=0; i<BUCKET_SIZE; i++) {
bucket[i] = new LinkedList<>();
}
// 정렬할 자릿수의 크기 만큼 반복한다.
// 현재 배열의 가장 큰 수는 10의 자리이므로, 2번 반복하게 한다.
int m = 1;
for(int d=0; d<2; d++) {
for(int i=0; i<len; i++) {
bucket[(A[i]/m)%10].add(A[i]);
}
for(int i=0, j=0; i<BUCKET_SIZE; i++) {
while(!bucket[i].isEmpty()) {
A[j++] = bucket[i].poll();
}
}
m *= 10;
}
}
}
|
cs |
4. 시간 복잡도
(1) 기수 정렬의 시간복잡도는 O(D*(N+B))이다.
( D: 길이가 가장 긴 자릿수 )
( B: 자릿수는 0~9까지이므로 고정 값 10 ) -> 코드에서는 BUCKET_SIZE
( N: 입력 데이터의 수 )
5. 공간 복잡도
(1) 주어진 배열 안에서 정렬이 일어나므로, 공간 복잡도는 O(n)이다.
6. 장점
(1) 대부분의 알고리즘들은 모두 데이터끼리의 직접적인 비교를 이용하는데, 그럴 경우 시간 복잡도는
O(NlogN)보다 작아질 수 없다. 그러나, 이 기수 정렬은 자릿수가 있는 데이터(정수, 문자열)를 직접적인 비교
없이 정렬을 수행하기 때문에, 시간복잡도가 O(N)으로 퀵 정렬보다 빠른 시간복잡도가 나오는 것이 가능하다.
(2) 가장 큰 장점은 반드시 끝까지 가지 않아도 중간에 정렬이 완료될 수 있다는 것이다.
( 단, 중간에 데이터를 점검해야 하므로 코드를 추가해야 한다. -> 구현이 복잡해진다. )
7. 단점
(1) 기수 정렬은 자릿수가 적 4바이트 정수 등에서나 제대로된 성능이 발휘되고 자릿수가 무제한에 가까운
문자열 정렬 등에 사용할 경우 오히려 퀵 정렬보다 느릴 수 있다.
(2) 만약 부동 소수점의 경우는 부호 여부, 지수부, 기수부에 대해 각각 기수정렬을 실행해야 하므로 까다로울 수 있다.
(3) 중간 결과를 저장할 BUCKET 공간이 필요하다.