[JAVA] 기수정렬(RadixSort)

	package kr.opid.sorting;
	import java.util.LinkedList;
	import java.util.Queue;
	public class RadixSort {
	public static void main(String[] args) {
	int[] array = new int[10];
	array[0] = 33;
	array[1] = 11;
	array[2] = 99;
	array[3] = 1;
	array[4] = 22;
	array[5] = 88;
	array[6] = 55;
	array[7] = 44;
	array[8] = 66;
	array[9] = 77;
	displayArray(array);
	array = radixSort(array);
	displayArray(array);
	}
	public static int[] radixSort(int[] input) {
	// Largest place for a 32-bit int is the 1 billion's place
	for (int place = 1; place <= 1000000000; place *= 10) {
	input = countingSort2(input, place);
	}
	return input;
	}
	// 방법 1
	private static int[] countingSort(int[] input, int place) {
	int[] out = new int[input.length];
	int[] count = new int[10];
	for (int i = 0; i < input.length; i++) {
	int digit = getDigit(input[i], place);
	count[digit] += 1;
	}
	for (int i = 1; i < count.length; i++) {
	count[i] += count[i - 1];
	}
	for (int i = input.length - 1; i >= 0; i--) {
	int digit = getDigit(input[i], place);
	out[count[digit] - 1] = input[i];
	count[digit]--;
	}
	return out;
	}
	// 방법 2
	private static int[] countingSort2(int[] input, int place) {
	int[] out = new int[input.length];
	Queue[] bucket = new Queue[10];
	for (int i = 0; i < 10; i++) {
	bucket[i] = new LinkedList<Integer>();
	}
	for (int i = 0; i < input.length; i++) {
	int digit = getDigit(input[i], place);
	bucket[digit].offer(input[i]);
	}
	int i = 0;
	int idx = 0;
	while (idx < 10) {
	if (bucket[i].size() != 0) {
	out[idx++] = (int) bucket[i].poll();
	} else {
	i++;
	}
	}
	return out;
	}
	private static int getDigit(int value, int digitPlace) {
	return ((value / digitPlace) % 10);
	}
	static void displayArray(int[] arr) {
	for (int i = 0; i < arr.length; i++) {
	System.out.print(arr[i] + " ");
	}
	System.out.println();
	}
	}

view raw RadixSort.java hosted with ❤ by GitHub