[정렬] counting sort

arr = [1, 2, 6, 2, 3, 2, 2, 4, 4]일 때,

정렬 결과는 [1, 2, 2, 2, 2, 3, 4, 4, 6]이 된다.

즉 중복 원소의 개수를 고려한다면, 인덱스의 개수가 정해진다는 것이다.

 

arr에 대해서, arr의 각 원소에 대한 빈도값을 담는 countingArr와

countingArr의 누적합을 담는 idxArr를 만들면, 아래와 같다.

 

countingArr = [0, 1, 4, 1, 2, 0, 1],

idxArr = [0, 1, 5, 6, 8, 8, 9]

 

coutingArr[n]의 의미는, arr에서 n이 countingArr[n]개 있다는 의미이다.

즉 countingArr[2] = 4라는 것은, arr에서 2가 4개 있다는 의미이다.

idxArr[n]의 의미는, sortedArr에서 n이 위치한 마지막 위치라는 의미이다.

즉 idxArr[2]=5의 의미는, sortedArr에서 2가 위치한 마지막 위치가 5라는 의미이다.

 

이 점을 이용하여 정렬할 수 있다.

 

arr를 마지막 원소부터 순회하는데, arr[i]의 값이 value라고 하면

resultArr[idxArr[value] - 1]에 value를 집어넣어준다.

여기서 -1을 해주는 것은, idxArr는 'n번째'의 개념이지 '인덱스 n'의 개념이 아니기 때문이다.

이것이 싫으면 idxArr를 만들 때부터 모든 원소를 -1로 초기화해두면 된다.

 

그리고 resultArr를 출력하면 끝난다.

 

O(n)의 시간복잡도를 가지지만,

배열의 원소의 개수가 아무리 적더라도 최댓값이 큰 경우에는

countingArr, indexArr가 어마무시하게 길어질 것이다.

 

class Main {
    public static int getMax(int a, int b) {
        if (a>=b) return a;
        else return b;
    }

    public static int[] countingSort(int[] arr) {
        int max = -1;
        for (int i = 0; i < arr.length; i++) {
            max = getMax(max, arr[i]);
        }

        /* create countingArr and indexArr */
        int[] countingArr = new int[max+1];
        int[] indexArr = new int[max+1];

        for (int i = 0; i < arr.length; i++) {
            countingArr[arr[i]]++;
        }

        indexArr[0] = countingArr[0];
        for (int i = 1; i < countingArr.length; i++) {
            indexArr[i] = indexArr[i-1] + countingArr[i];
        }

        /* create resArr */
        int resArrLength = indexArr[max];
        int[] resArr = new int[resArrLength];

        for (int i = arr.length - 1; i >= 0; i--) {
            int curValue = arr[i];
            resArr[indexArr[curValue]-- - 1] = curValue;
            // indexArr[n]은 마지막 n이 indexArr[n]번째(예: 5번째)에 위치해 있다는 것으로서
            // 실제 마지막 n의 인덱스는 indexArr[n]-1(예: 4번째)이다.
        }

        return resArr;
    }

    public static void main(String[] args) {
        // input
        int[] arr = {3, 5, 0, 0, 1, 3, 6, 5, 4, 5};

        // sort
        int[] res = countingSort(arr);

        // print
        for (int i = 0; i < res.length - 1; i++) {
            System.out.printf("%d ", res[i]);
        }
    }
}