기수 정렬 Radix Sort

Intro::

기수 정렬에 대해 알아보자.

정의

기수 정렬은 정수와 같은 키를 기준으로 데이터를 정렬하는 비교 기반 정렬 알고리즘이 아닌, 자릿수별로 정렬을 수행하여 전체 리스트를 정렬하는 방식입니다. 기수 정렬은 특히 숫자의 크기가 클 때 유용하며, 최하위 자릿수(LSD: Least Significant Digit) 방식과 최상위 자릿수(MSD: Most Significant Digit) 방식으로 구현 가능합니다.

시간복잡도

O(d * (n + b)) → d는 자릿수, b는 10

코드

package algorithm;

import java.util.*;

public class RadixSort {
	// 기수 정렬 함수
	public static void radixSort(int[] arr) {
		// 배열 중 최대값 찾기
		int max = Arrays.stream(arr).max().getAsInt();
		// 최대 자릿수만큼 반복
		for (int exp = 1; max / exp > 0; exp *= 10) {
			countSort(arr, exp);
		}
	}

	// exp는 현재 정렬할 자릿수를 의미 (1 -> 10 -> 100 -> ...)
	private static void countSort(int[] arr, int exp) {
		int n = arr.length;
		int[] output = new int[n]; // 정렬된 배열을 담을 공간
		int[] count = new int[10]; // 숫자의 빈도수를 저장할 배열 (0-9)
		// 현재 자릿수(exp)에 따른 빈도수 계산
		for (int i = 0; i < n; i++) {// 0:2, 2:2, 4:1, 5:2, 6:1
			count[(arr[i] / exp) % 10]++;
		}
		// 누적 합계 계산
		for (int i = 1; i < 10; i++) {
			count[i] += count[i - 1];
		}
		// 누적 합계를 이용하여 출력 배열을 생성
		for (int i = n - 1; i >= 0; i--) {
			output[count[(arr[i] / exp) % 10] - 1] = arr[i];
			count[(arr[i] / exp) % 10]--;
		}

		// 정렬된 배열을 원래 배열에 복사
		for (int i = 0; i < n; i++) {
			arr[i] = output[i];
		}
		System.out.println(exp + "자리수: " + Arrays.toString(arr));
	}

	public static void main(String[] args) {
		int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
		radixSort(arr);
		System.out.println("정렬된 배열: " + Arrays.toString(arr));
	}
}

References::