[자료구조 복습12] Radix Sort 기수정렬

해당 글은 geeks for geeks와 위키피디아 를 참고하여 쓰여졌습니다. 

먼저 Radix sort가 어떻게 동작하는지 알아보자.

Radix Sort는 요소 간의 비교 없이 동작하는 소팅 알고리즘 이다. 단순하게 생각하면 최댓값 n개의 배열을 만들고,

해당하는 수를 인덱스로 하는 배열 요소의 빈도수를 증가시킨 후 , 다시 배열을 돌면서 빈도수만큼 해당 인덱스를 출력해도 된다. 하지만 배열이 [1,2,10000,999,80] 이렇게 생긴 경우는 효율성이 매우 떨어진다.

 

이를 위해서 각 자리수를 비교해 나가며 정렬하는 Radix Sort를 학습해보자.

배열 [170, 45, 75 , 90 , 802 , 24 , 2 , 66 ] 을 예시로 들어보자.

1의자리수부터 최댓값 n의 최대 자리수까지 본다. 해당 자리수가 없는 요소들은 해당 자리수를 0이라고 계산한다.

위의 예시는 1의자리수, 10의 자리수, 100의 자리수의 순서대로 정렬 되었다. 

즉 1의 자리수부터 정렬 하고, 1의 자리수에서 정렬된 순서대로 다시 10의 자리수로 정렬한다. 이렇게 되면 마지막엔 당연히 모든 자리수에 대하여 정렬이 된다.

더 쉽게 이해하고자 한다면, 

'큐'의 형태를 떠올리면 된다. 170, 80 , 71 요소를 큐에 넣을 때,

1의 자리  0: 170 80  / 1: 71 

10의 자리 7: 170, 71 /  8: 80

100 의 자리 0: 71, 80  / 1: 170 

-> 71, 80. 170 이렇게 정렬 된다. 해당 알고리즘도 똑같은 원리로 정렬하나 , 다른 점은 자료구조 큐를 사용하지 않는다는 것이다.

그럼 하나하나씩 살펴보도록 하자

 

일단 전체 radix sort의 로직은 이러하다.

1) 최대 자리수를 알아야하므로 먼저 주어진 배열에서 최댓값을 찾는다 

static int get_max(int arr[], int n) {
	int max=arr[0];
	for(int i=1 ; i< n; i++) {
		if(arr[i]>max) max=arr[i]; }	
	return max; }

2) 1부터 시작해 최대자리수 까지 count sort를 한다.

static void radixSort(int arr[] , int n) {
	int m = get_max(arr,n);
	for(int exp=1; m/exp>0; exp*=10)
		countSort(arr,n,exp);}

 

그 다음 중요한 count sort의 로직은 이러하다 

1) 정렬 된 요소를 집어넣을 output 배열을 주어진 배열 arr의 크기 n 만큼 선언 / count sort 빈도수를 저장할 배열을 10의 크기만큼 선언한다.

2) 주어진 배열의 exp자리수 (매개변수로 주어진 자리수)를 계산하여 해당 자리수의 빈도수를 count 배열에 연산한다.

3) 연산된 count배열을 arr[i] += arr[i-1] 하여, output 배열에 각각의 요소들이 들어갈 인덱스를 연산한다.

4) count배열의 요소들을 통해 output배열 인덱스에 arr배열의 뒤부터 삽입한다. 

5) arr배열에 output배열을 복사한다

static void countSort(int arr[], int n, int exp) {
	int output[] = new int[n]; //for storing result 
	int i;
	int count[] = new int[10]; //for counting 

	for(i=0; i<n ;i++)  //각각 자리수에 맞춰서 증가 
		count[(arr[i]/exp)%10]++;
		
	for(i=1; i<10; i++) //output 배열 인덱스
		count[i]+=count[i-1];		
		
	for(i = n-1; i>=0; i--) { //output배열에 정렬 
		output[count[(arr[i]/exp)%10]-1]=arr[i];
		count[(arr[i]/exp)%10]--;}

	for(i=0; i<n; i++) 
		arr[i]=output[i]; 
}

 

 

위의 count sort에서 헷갈릴법한 3) 4)번을 살펴보자

예시로, 각각 빈도수가

0: 0

1: 2

2: 1

3: 0

4: 3 일때를 보자 

 

3번 알고리즘대로 구현하면 count 배열은 아래와 같이 값이 변한다. 

변한 값은 뒤의 숫자 arr[i-1]+arr[i]로, 각 빈도수에 해당하는 숫자들이 output배열에 들어갈 수 있는 인덱스의 내림차순임을 알 수 있다.

 

즉, "자리수 2" 의 경우, 자리수 2보다 앞에 와야할 숫자가 2개가(자리수 1의 빈도수 2 ) 이미 있고, 자리수 2는 1개의 숫자만 가지고 있으니 3번째 자리에 올 수 있다는 것이다. 하지만 실제로 배열은 0부터 시작하므로 -1을 해주어야 한다.

 

그리고 자리수 4를 보면, 마찬가지로 자리수 4보다 앞에 와야할 숫자가 5개 있고 (자리수1+자리수2) 자리수 4의 숫자는 3개이므로 자리수 4가 들어갈 인덱스는 6 , 5 , 4 (실제로는 5, 4, 3) 인 것이다.

 

이런식으로 count 배열의 값을 변경해준뒤, arr 배열의 맨 뒤 숫자부터 0까지 output에 올바른 인덱스를 찾아 삽입한다.맨 뒤부터 삽입하는 이유는, 이미 앞의 자리수가 정렬 되었다고 가정하기 때문이다. 왜냐하면 위에서도 알 수 있듯 가능한 인덱스의 뒤부터 숫자를 삽입하기 때문이다. 

따라서,

output[count[(arr[i]/exp)%10]-1] = arr[i]

arr[i]의 자리수에 해당하는 count 배열을 찾고, count 배열에 저장되어 있는 수 -1 (배열은 0부터 시작하므로) 에 arr[i]를 넣는다.  

count[(arr[i]/exp)%10] -- ;

count배열에 저장되어 있는 수를 하나 감소시켜야만, 자리수가 같은 숫자가 들어 올 때 그 다음 인덱스에 저장된다.

 

 

 

 

 

Radix Sort JAVA 전체 소스코드 

public class RadixSort {
	static int get_max(int arr[], int n) {
		int max=arr[0];
		for(int i=1 ; i< n; i++) {
			if(arr[i]>max) max=arr[i]; }
		
		return max;
	}
	
	static void countSort(int arr[], int n, int exp) {
		int output[] = new int[n]; //for storing result 
		int i;
		int count[] = new int[10]; //for counting 

		for(i=0; i<n ;i++)  //각각 자리수에 맞춰서 증가 
			count[(arr[i]/exp)%10]++;
		
		for(i=1; i<10; i++) 
			count[i]+=count[i-1];	
		
		for(i = n-1; i>=0; i--) {
			output[count[(arr[i]/exp)%10]-1]=arr[i];
			System.out.println(output[count[(arr[i]/exp)%10]-1]);
			count[(arr[i]/exp)%10]--;
		}
		
		System.out.println("--");
		for(i=0; i<n; i++) {
			arr[i]=output[i];
			System.out.println(i+" "+output[i]);
		}
	}
	
	static void radixSort(int arr[] , int n) {
		int m = get_max(arr,n);
		for(int exp=1; m/exp>0; exp*=10)
			countSort(arr,n,exp);
		
	}
	
	static void print(int arr[], int n) { //배열 print 메서드 
		for(int i=0; i<n ;i++)
			System.out.println(arr[i]+" ");
	}
	
	public static void main(String[] args){
		int arr[] = {170, 45, 75, 90, 802, 24, 2, 66}; 
        int n = arr.length; 
        radixSort(arr,n);
        print(arr,n);
	}	
}

 

- Radix Sort의 시간복잡도

 

입력 리스트가 n개의 정수를 가지고 있을 때, 내부 루프들은 n번 반복되며 , 외부 루프는 최대자리수 d 만큼 반복된다.

즉 O(d*n) 이 된다. 

하지만 d는 n에 비하면 매우 작기때문에 O(n) 이라고 해도 무리 없을 것이다.

또한 Radix Sort는 in-Place 알고리즘이 아니기 때문에 그만큼 메모리가 더 필요하다.