기수 정렬(Radix Sort)

기수 정렬(Radix Sort)

정렬할 원소의 키 값에 해당하는 버킷(bucket)에 원소를 분배했다가 순서대로 꺼내는 방법으로 정렬. 기수만큼의 버킷이 필요하다.

기수란 즉 '자릿수'이므로 10진수 원소들을 정렬할 때는 0~9 까지의 10개의 버킷을 사용한다.

일의 자리에 대해서 정렬한 후 십의 자리에 대해 정렬 그 다음은 백의 자리에 대해서 정렬하는 방법을 이용한다.

​

정렬할 원소의 수 n과 키 값의 자릿수 d와 버킷의 수를 결정하는 기수 r에 따라 수행시간이 달라진다.

시간 복잡도는 O(d(n+r))이 된다.

​

예시)

{57, 16, 41, 2, 50, 6, 32, 31}

​

1. 0~9 까지의 10개의 버킷을 만든다.

버킷 0 ---- [ ]

버킷 1 ---- [ ]

버킷 2 ---- [ ]

버킷 3 ---- [ ]

버킷 4 ---- [ ]

버킷 5 ---- [ ]

버킷 6 ---- [ ]

버킷 7 ---- [ ]

버킷 8 ---- [ ]

버킷 9 ---- [ ]

​

2. 일의 자리에 대하여 기수 정렬을 수행한다.

버킷 0 ---- [ 50 ]

버킷 1 ---- [ 31, 41 ]

버킷 2 ---- [ 2, 32 ]

버킷 3 ---- [ ]

버킷 4 ---- [ ]

버킷 5 ---- [ ]

버킷 6 ---- [ 6, 16 ]

버킷 7 ---- [ 57 ]

버킷 8 ---- [ ]

버킷 9 ---- [ ]

===> 순서대로 꺼내기

{50, 31, 41, 2, 32, 6, 16, 57}

​

3. 십의 자리에 대하여 기수 정렬을 수행한다.

버킷 0 ---- [ 2, 6 ]

버킷 1 ---- [ 16 ]

버킷 2 ---- [ ]

버킷 3 ---- [ 31, 32 ]

버킷 4 ---- [ 41 ]

버킷 5 ---- [ 50, 57 ]

버킷 6 ---- [ ]

버킷 7 ---- [ ]

버킷 8 ---- [ ]

버킷 9 ---- [ ]

===> 순서대로 꺼내기

{2, 6, 16, 31, 32, 41, 50, 57}

​

프로그램 작성)

package test;

class Sort {
	public void RadixSort(int[] a, int base) {
		int size = a.length;
		int max = getMax(a);
		
		for(int i=1; i<=max; i*=base) {
			int[] count = new int[base];
			int[] output = new int[size];
			
			for(int j=0; j<size; j++) {
				count[(a[j]/i)%base]++;
			}
			
			for(int j=1; j<base; j++) {
				count[j]+= count[j-1];
			}
			
			for(int j=size-1; j>-1; j--) {
                int k = (a[j]/i)%base;
                output[count[k]-1] = a[j];
                count[k]--;
            }
			
            for(int j=0; j<size; j++) {
            	a[j]=output[j];
            }
		}
	}
	
	public int getMax(int[] a) {
		int max = a[0];
		
		for(int i=1; i<a.length; i++) {
			if(a[i] > max) {
				max = a[i];
			}
		}
		
		return max;
	}
}

public class Test {
	public static void main(String[] args) {
		int a[] = {57, 16, 41, 2, 50, 6, 32, 31};

		System.out.println("정렬 전 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
		System.out.println();

		Sort s = new Sort();
		s.RadixSort(a, 10);

		System.out.println("정렬 후 원소 : ");
		for(int i=0; i<a.length; i++) {
			System.out.printf(" %d", a[i]);
		}
	}
}

실행 결과)