기수 정렬 (Radix Sort)

 

1. 개요

• 숫자의 각 자릿수를 기준으로 정렬하는 비교 기반 정렬 알고리즘이 아닌, 분배식 정렬 방법이다.
• 데이터의 자릿수를 기준으로 순차적으로 정렬을 진행하며, 가장 낮은 자릿수(1의 자리)부터 시작하여 가장 높은 자릿수까지 차례대로 정렬하는 과정을 거친다.
• 데이터의 크기에 비해 상대적으로 자릿수가 작을 때 좋은 성능을 보인다.

---

2. 특징

• 시간복잡도: O(d(n+k))
• n은 정렬할 요소의 개수, d는 자릿수의 개수, k는 기수(10진수인 경우 10)
• 공간 복잡도: O(n + k)
• 기수 정렬은 정렬을 위한 임시 배열 공간을 필요로 한다. 자릿수가 클수록 메모리 사용량이 많아진다.

---

3. 코드

import java.util.Arrays;

public class RadixSortTest {

	public static void main(String[] args) {
		int[] data = { 170, 45, 75, 90, 802, 24, 2, 66 };

		radixSort(data);

		System.out.println(Arrays.toString(data));
	}

	public static void radixSort(int[] arr) {
		final int RADIX = 10; // 10진수 체계 사용
		int max = arr[0];

		for (int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		for (int exp = 1; max / exp > 0; exp *= RADIX) { // exp: 자리수
			countSort(arr, exp);
		}
	}

	private static void countSort(int[] arr, int exp) {
		int[] output = new int[arr.length];
		int[] count = new int[10];

		// count 배열 초기화
		for (int i = 0; i < arr.length; i++) {
			count[(arr[i] / exp) % 10]++;
		}

		// count 배열을 변경하여 실제 위치를 반영하도록 함
		for (int i = 1; i < 10; i++) {
			count[i] += count[i - 1];
		}

		// 결과 배열을 채움
		for (int i = arr.length - 1; i >= 0; i--) {
			output[count[(arr[i] / exp) % 10] - 1] = arr[i];
			count[(arr[i] / exp) % 10]--;
		}

		// 원래 배열에 결과를 복사
		for (int i = 0; i < arr.length; i++) {
			arr[i] = output[i];
		}
	}

}