Radix Sort

* Radix Sort

* Counting Sort를 활용

알고리즘

package algo.radix;

import java.util.Arrays;

public class MyRadixSort {

	private int[] itemArr;
	private Integer[] sortedItemArr;
	private int[] countingArr;
	
	public void sort(int[] arr) {
		
		this.itemArr = arr;
		this.sortedItemArr = new Integer[itemArr.length];
		this.countingArr = new int[10];
		
		int maxItem = getMax();
		
		for(int i = 1 ; maxItem / i > 0 ; i*=10) {
			countSort(i);
		}
	}
	
	private void countSort(int div) {
		
		Arrays.fill(sortedItemArr, 0);
		Arrays.fill(countingArr, 0);
		
		printArr(itemArr, "시작 배열           -> ");
		
		//자릴수에 따라 카운팅 및 정렬
		int item = 0;
		for(int i = 0 ; i < itemArr.length ; i++) {
			item = itemArr[i] / div % 10;
			countingArr[item] = countingArr[item] + 1;
		}
		
		printArr(countingArr, "카운팅 배열        -> ");
		
		int sum = 0;
		for(int i = 0 ; i < countingArr.length ; i++) {
			sum += countingArr[i];
			countingArr[i] = sum;
		}
		
		System.out.println("* 정렬 시작");
		
		int targetIdx = 0;
		for(int i = itemArr.length - 1 ; i >= 0 ; i--) {
			
			item = itemArr[i] / div % 10;
			targetIdx = countingArr[item];
			sortedItemArr[targetIdx-1] = itemArr[i];
			countingArr[item] = countingArr[item] - 1;
			
			printArr(countingArr, "\t카운팅 누적 배열 \t-> ");
			printIntegerArr(sortedItemArr, "\t정렬된 배열1\t-> ");
			
		}
		
		for(int i = 0 ; i < sortedItemArr.length ; i++) {
			itemArr[i] = sortedItemArr[i];
		}
		
		printArr(itemArr, "\t정렬된 배열2\t-> ");

	}
	
	private int getMax() {
		
		int max = itemArr[0];
		for (int i = 0; i < itemArr.length; i++) {

			if (itemArr[i] > max)
				max = itemArr[i];

		}
		
		return max;
	}
	
	private void printArr(int[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
	private void printIntegerArr(Object[] targetArr, String msg) {

		System.out.print(msg);
		for (int i = 0; i < targetArr.length ; i++)
			System.out.print(targetArr[i] + " ");
		System.out.println();

	}
	
}

테스트

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

import algo.countingsort.MyCountingSort;
import algo.radix.MyRadixSort;

public class Main {

	public static void main(String[] args) {

		MyRadixSort algo = new MyRadixSort();
		algo.sort(new int[] {170, 45, 75, 90, 802, 24, 2, 66});
		
	}

}

[결과]
시작 배열           -> 170 45 75 90 802 24 2 66 
카운팅 배열        -> 2 0 2 0 1 2 1 0 0 0 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 4 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 0 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 5 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 0 0 0 66 
	카운팅 누적 배열 	-> 2 2 3 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 0 2 24 0 0 66 
	카운팅 누적 배열 	-> 2 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 0 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 7 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 0 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 6 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 0 75 66 
	카운팅 누적 배열 	-> 1 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 0 90 802 2 24 45 75 66 
	카운팅 누적 배열 	-> 0 2 2 4 4 5 7 8 8 8 
	정렬된 배열1	-> 170 90 802 2 24 45 75 66 
	정렬된 배열2	-> 170 90 802 2 24 45 75 66 
시작 배열           -> 170 90 802 2 24 45 75 66 
카운팅 배열        -> 2 0 1 0 1 0 1 2 0 1 
* 정렬 시작
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 7 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 0 0 
	카운팅 누적 배열 	-> 2 2 3 3 4 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 0 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 3 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 0 45 66 0 75 0 
	카운팅 누적 배열 	-> 2 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 0 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 1 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 0 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 8 
	정렬된 배열1	-> 802 2 24 45 66 0 75 0 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 6 7 7 
	정렬된 배열1	-> 802 2 24 45 66 0 75 90 
	카운팅 누적 배열 	-> 0 2 2 3 3 4 4 5 7 7 
	정렬된 배열1	-> 802 2 24 45 66 170 75 90 
	정렬된 배열2	-> 802 2 24 45 66 170 75 90 
시작 배열           -> 802 2 24 45 66 170 75 90 
카운팅 배열        -> 6 1 0 0 0 0 0 0 1 0 
* 정렬 시작
	카운팅 누적 배열 	-> 5 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 0 90 0 0 
	카운팅 누적 배열 	-> 4 7 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 0 0 
	카운팅 누적 배열 	-> 4 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 0 75 90 170 0 
	카운팅 누적 배열 	-> 3 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 0 66 75 90 170 0 
	카운팅 누적 배열 	-> 2 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 0 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 1 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 0 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 8 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 0 
	카운팅 누적 배열 	-> 0 6 7 7 7 7 7 7 7 8 
	정렬된 배열1	-> 2 24 45 66 75 90 170 802 
	정렬된 배열2	-> 2 24 45 66 75 90 170 802