기수 정렬, 계수 정렬 java 예시 코드

기수정렬

public class Main {
    // 기수정렬 -> 큐를 이용하여 낮은 자리수부터 비교..
    private static void radixSort(int[] arr) {
        Queue<Integer>[] queueArr = new Queue[10]; //0부터 9까지
        for (int i = 0; i < queueArr.length; i++) {
            queueArr[i] = new LinkedList<>();
        }

        int maxLen = getMaxLen(arr);

        int div = 1;
        int idx = 0;
        for (int i = 0; i < maxLen; i++) { // 최대 자리수 만큼 반복
            for (int j = 0; j < arr.length; j++) {
                queueArr[(arr[j] / div) % 10].add(arr[j]); // 특정 수의 자리수 구하는 방법 !
            }

            for (int j = 0; j < queueArr.length; j++) {
                while (!queueArr[j].isEmpty()) {
                    arr[idx++] = queueArr[j].poll();
                }
            }
            div *= 10;
            idx = 0;
        }
    }

    private static int getMaxLen(int[] arr) {
        int maxLen = 0;
        for (int i = 0; i < arr.length; i++) {
            int len = (int) Math.log10(arr[i]) + 1;
            if (maxLen < len) {
                maxLen = len;
            }
        }
        return maxLen;
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 52, 27, 48, 17, 99, 56};
        radixSort(arr);
        System.out.println("기수 정렬: " + Arrays.toString(arr));
    }
}

 

계수정렬

public class Main2 {

    public static void countingSort(int[] arr) {
        int maxNumber = Arrays.stream(arr).max().getAsInt(); // 스트림으로 최대값 구하기
        int[] countSortArr = new int[maxNumber + 1];
        for (int number : arr) {
            countSortArr[number]++;
        }

        int idx = 0;
        for (int i = 0; i < countSortArr.length; i++) {
            if (countSortArr[i] > 0) {
                while (countSortArr[i] > 0) { //count배열열 0이 될때까지 빼기..!
                    arr[idx++] = i; //count배열의 인덱스가 정렬배열의 값이 된다..!
                    countSortArr[i]--;
                }
            }
        }
    }

    public static void main(String[] args) {
        // Test code
        int[] arr = {10, 32, 10, 27, 32, 17, 99, 56};
        countingSort(arr);
        System.out.println("계수 정렬: " + Arrays.toString(arr));
    }
}