기수 정렬(Radix Sort)

이번에 배워볼 정렬 알고리즘은 기수 정렬(Radix Sort)이다.

지금까지 배워온 정렬들은 모두 데이터들을 비교하여 정렬하는 방식이었다. 기수 정렬은 이와는 다르게 데이터를 비교하지 않고 정렬하는 조금 특수한 정렬 알고리즘이다. 기수 정렬은 O(dn)의 시간 복잡도를 가질 정도로 매우 빠른 정렬 알고리즘이다. 여기서 d는 데이터의 자릿수이다.

​

기수 정렬은 아쉽게도 추가적인 메모리를 필요로 하며, 정렬할 수 있는 데이터 타입이 제한된다는 단점이 있다. 기수 정렬을 사용하기 위해선 데이터의 값들이 동일한 길이를 가지는 숫자나 문자열로 구성되어 있어야 한다.

​그렇다면 0~99 사이의 숫자들로 이루어진 배열을 정렬하는 과정을 살펴보자. 간단하게 100개의 배열을 생성하여 각 인덱스에 저장하여 출력하는 방법도 있겠지만, 조금 더 효율적으로 생각해보면 1의 자릿수와 10의 자릿수를 따로따로 사용하여 정렬을 하면 10개의 배열만 사용하여도 정렬이 가능해진다. 주의해야 할 점은 낮은 자릿수부터 정렬을 해야 한다.

​

예를 들어 {28, 93, 39, 81, 62, 72, 38, 26}로 구성된 배열이 있다고 해보자. 먼저 1의 자릿수로 정렬을 하게 되면 {81, 62, 72, 93, 26, 28, 38, 39}로 정렬이 될 것이다. 이제 10의 자릿수로 정렬을 하게 되면 {26, 28, 38, 39, 62, 72, 81, 93}으로 배열의 원소들이 정렬된 것을 확인할 수 있다.

 

기수 정렬(Radix Sort)의 시간 복잡도는 O(dn)이다.
다만, 추가적인 메모리가 필요하며, 정렬할 수 있는 레코드의 타입이 제한된다.

 

 

기수 정렬을 Java로 구현한 코드는 다음과 같다.

import java.util.LinkedList;
import java.util.Queue;

public class Main {

	static final int bucketSize = 10;
	
	public static void main(String[] args) {
		int[] arr = {28, 93, 39, 81, 62, 72, 38, 26};
		
		radix_Sort(arr.length, arr);
		
		for (int i = 0; i < arr.length; ++i) {
			System.out.print(arr[i] + " ");
		}
	}
	
	public static void radix_Sort(int n, int[] arr) {
		//bucket 초기화
		Queue<Integer>[] bucket = new LinkedList[bucketSize];
		for (int i = 0; i < bucketSize; ++i) {
			bucket[i] = new LinkedList<>();
		}
		
		int factor = 1;
		
		//정렬할 자릿수의 크기 만큼 반복한다.
		for (int d = 0; d < 2; ++d) {
			for (int i = 0; i < n; ++i) {
				bucket[(arr[i] / factor) % 10].add(arr[i]);
			}
			
			for (int i = 0, j = 0; i < bucketSize; ++i) {
				while (!bucket[i].isEmpty()) {
					arr[j++] = bucket[i].poll();
				}
			}
			
			factor *= 10;
		}
	}
}