이론

기수 정렬은(radix sort)은 값을 비교하지 않는 특이한 정렬이다. 기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다. **기수 정렬의 시간 복잡도는 O(kn)**으로, k는 데이터의 자릿수를 말한다.

기수 정렬 수행 방식

1. 수 정렬하기3

1.1. 문제 설명

1.2. 문제 분석

1.3. 슈도코드

1.4. 구현

public class 수_정렬하기3 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scan.nextInt();
        }

        radixSort(arr);

        for(int i : arr){
            System.out.println(i);
        }
    }

    public static void radixSort(int[] arr) {
        // 가장 큰 자릿수 찾기
        int maxDigit = getMaxDigit(arr);

        // 자릿수별로 정렬
        for (int i = 1; i <= maxDigit; i++) {
            countingSort(arr, i);
        }
    }

    // 배열에서 가장 큰 자릿수를 찾는 메소드
    private static int getMaxDigit(int[] arr) {
        int maxDigit = 1;
        int base = 10;
        for (int num : arr) { // 108
            int curDigit = 1;
            while (num >= base) {
                base *= 10;
                curDigit++;
            }
            if (curDigit > maxDigit) {
                maxDigit = curDigit;
            }
        }
        return maxDigit;
    }

    // 자릿수 기준으로 counting sort를 수행하는 메소드
    private static void countingSort(int[] arr, int digit) {
        int[] countingArray = new int[10];
        int[] outputArray = new int[arr.length];
        int divisor = (int) Math.pow(10, digit - 1);

        // 자릿수 기준으로 counting array를 채움
        for (int num : arr) {
            int index = (num / divisor) % 10; // 8/1 % 10 = 8
            countingArray[index]++;
        }

        // counting array를 누적합 배열로 변경
        for (int i = 1; i < countingArray.length; i++) { // countingArr = [2, 2, 7, 1, ...]
            countingArray[i] += countingArray[i - 1]; // 2,4,11,12 ...
        }

        // output array에 숫자 삽입
        for (int i = arr.length - 1; i >= 0; i--) {
            int index = (arr[i] / divisor) % 10;
            outputArray[countingArray[index] - 1] = arr[i];
            countingArray[index]--;
        }

        // output array를 원래 배열에 복사
        for (int i = 0; i < arr.length; i++) {
            arr[i] = outputArray[i];
        }
//        System.arraycopy(outputArray, 0, arr, 0, arr.length);
    }
}

public class 수_정렬하기3_2_10989 {

    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = scan.nextInt();
        }

        int maxDigit = getMaxDigit(arr);

        radixSort(arr, maxDigit);

        for (int i : arr) {
            System.out.println(i);
        }
    }

    private static int getMaxDigit(int[] arr) {
        int maxDigit = 1;
        int base = 10;
        for (int num : arr) {
            int curDigit = 1;
            while (num >= base) {
                base *= 10;
                curDigit++;
            }
            if (curDigit > maxDigit) {
                maxDigit = curDigit;
            }
        }
        return maxDigit;
    }

    public static void radixSort(int[] arr, int maxSize) {
        int[] output = new int[arr.length];
        int jarisu = 1;
        int count = 0;
        while (count != maxSize) { // 최대 자릿수만큼 반복
            int[] bucket = new int[10];
            for (int i = 0; i < arr.length; i++) {
                bucket[(arr[i] / jarisu) % 10]++; // 1의 자리부터 시작
            }
            for (int i = 1; i < 10; i++) {
                bucket[i] += bucket[i - 1]; // 누적합 배열을 이용해 index 계산
            }
            for (int i = arr.length - 1; i >= 0; i--) { // 현재 자릿수를 기준으로 정렬
                output[bucket[arr[i] / jarisu % 10] - 1] = arr[i];
                bucket[(arr[i] / jarisu % 10)]--;
            }
            for (int i = 0; i < arr.length; i++) {
                arr[i] = output[i]; // 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장
            }
            jarisu *= 10;
            count++;
        }
    }

}