Counting Sort(카운팅 정렬)

기본 아이디어: 배열의 있는 숫자들의 개수를 센 뒤 크기에 따라서 배열을 정렬해준다. 카운팅정렬은 안정정렬이다.

작동방식
1. 배열(arr)에서 가장 큰 값을 찾는다. 이 값이 개수를 세어주는 배열의 길이가 된다.
2. 숫자들의 개수를 저장하는 배열(countArr)을 만들고 원래 배열(arr)을 돌면서 해당 숫자를 countArr의 인덱스로 해서 숫자의 개수 정보를 저장한다.
3. countArr의 값을 누적합으로 변경한다. 누적합으로 변경한 countArr은 인덱스에 해당하는 숫자 앞에 몇 개의 숫자가 있는지에 대한 정보를 담고 있다.
4. arr배열을 거꾸로 순회하면서(안정정렬을 위함) arr배열의 값을 countArr의 인덱스 사용하여 countArr의 값을 꺼내서 -1을 해주고 그 값을 다시 arr배열의 인덱스로 하여 결과 배열(resultArr)에 넣어준다.

설명이 어려워 코드로 보는게 편할거같다....

시간복잡도: O(n)

시간복잡도를 보면 매우 뛰어난 성능을 보이는 것 같지만 정렬하고자하는 숫자의 범위가 숫자의 개수에 비해 너무 넓으면 메모리 낭비가 심해진다. 예를 들어 정렬하고자하는 숫자가 1~10억이지만 숫자의 개수가 3개이면 3개의 숫자를 정렬하기 위해 10억의 길이를 갖는 배열을 만들어야하는 비효율이 발생한다.

java 코드

private static int[] countingSort(int[] arr, int size) {
        int max = 0;
        int[] resultArr = new int[size];

		// countArr 배열의 길이를 알기 위함
        for(int i = 0; i < arr.length; i++){
            if(arr[i] > max) max = arr[i];
        }
		
        // 인덱스가 0부터 시작하므로 정렬하고자 하는 숫자가 포함될 수 있도록 길이에 1을 더해준다.
        int[] countArr = new int[max+1];

        // 배열에 있는 숫자들이 각각 몇개가 있는지 체크하고 각 숫자들에 해당하는 idx에 저장
        for(int i = 0 ; i < arr.length; i++){
            ++countArr[arr[i]];
        }

        // 개수를 누적합으로 다시 계산
        for(int i = 0 ; i < countArr.length-1; i++){
            countArr[i+1] += countArr[i];
        }

        // 원래 배열을 거꾸로 돌면서(안정정렬) 개수를 저장한 배열에 있는 정보를 이용해서 크기 순으로 정렬
        for(int i = arr.length-1; i >= 0; i--){
            resultArr[--countArr[arr[i]]] = arr[i];
        }

        return resultArr;
    }

코드에 오류가 있으면 말씀해주세요.