어떤 기수 r을 이용하여 정렬 키를 몇 개의 숫자로 분해
기수-r 정렬에서는 r개의 빈(bin)이 필요
기수 정렬은 정렬 순서상 앞서고 뒤섬의 판단을 위한 비교연산을 하지 않음
정렬 대상의 모든 길이가 동일해야 가장 효율적
※ 좋은 예) [123, 486, 309, 944], [blue, rice, pain, book] 등등
※ 나쁜 예) [5643, -43, 1, 87912], [sky, pencil, water, a] 등등
길이가 각각 다를경우 빈 공간을 메꿔야하는 추가 작업 발생 → 성능 저하
정렬 대상의 자리수를 기준으로 '버킷'이라는 공간에 '큐(Queue)' 방식으로 저장 후 다시 꺼냄
성능이 키의 크기와 r의 선택에 영향을 받음
정렬할 숫자들을 '버킷' 공간에 각 숫자와 동일한 위치에 저장
'버킷' 공간에 저장된 숫자들을 처음부터 다시 꺼내어 정렬 공간에 차례대로 저장
※ 버킷 공간의 크기는 숫자 길이와 동일
숫자 '134, 224, 232, 122'를 오름차순으로 정렬
숫자 '134, 224, 232, 122'를 오름차순으로 정렬
import java.util.Arrays;
public class Main{
static final int N = 10;
public static void main(String[] args) {
int[] arr = new int{134, 224, 232, 122};
System.out.println("정렬 전: " + Arrays.toString(arr));
radixSort(arr);
System.out.println("정렬 후: " + Arrays.toString(arr));
}
public static void radixSort(int[] array) {
final int MAX_LENGTH = getMaxLength(array), myArrLen = array.length;
int myRadix = 1;
int[] sortedArray = new int[myArrLen], counts;
for (int p = 0; p < MAX_LENGTH; p++) {
counts = new int[10];
for (int numOfTemp : array) {
counts[(numOfTemp / myRadix) % 10]++;
}
for (int i = 1; i < 10; i++)
counts[i] += counts[i - 1];
for (int i = myArrLen - 1; i >= 0; i--) {
sortedArray[counts[(array[i] / myRadix) % 10]-- - 1] = array[i];
}
array = sortedArray;
sortedArray = new int[myArrLen];
myRadix *= 10;
}
System.out.println("정렬 후 : " + Arrays.toString(array));
}
public static int getMaxLength(int[] array) {
int max = 0;
for (int numOfTemp : array) {
if (max < numOfTemp)
max = numOfTemp;
}
return (int) Math.log10(max) + 1;
}
}
reference