[JAVA] 계수정렬(Counting Sort) 개념과 코드 구현

계수정렬(Counting Sort)은 정수 정렬 알고리즘의 하나로

각 숫자(키)가 몇번 등장했는지 계수(카운팅)해서 각 키값의 위치를 정하는 알고리즘이다.

배열의 값의 범위가 제한되어있을때 효율으로 작동하지만, 입력값의 범위가 크면 카운트 배열이 커지므로 메모리 문제가 생길 수 있다.

구분	최악 시간복잡도	최선 시간복잡도	평균 시간복잡도	공간복잡도(메모리)	안정성
계수정렬	O(n + k)	O(n + k)	O(n + k)	O(n + k)	Y

* n: 정렬할 배열 길이, k: 정수의 범위

 

알고리즘

1. 입력 배열의 최댓값과 최솟값을 구한다.

2. 최솟값부터 최댓값까지의 범위를 가지는 배열을 만든다. (카운트 배열)

3. 배열의 각 요소들이 몇번 등장하는지를 카운트 배열에 저장한다.

4. 카운트 배열의 누적합을 구한다. (배열에서 요소들이 위치할 인덱스 결정에 사용)

5. 배열을 역순으로 순회하면서 요소의 등장횟수를 통해 인덱스를 결정하고 해당 인덱스에 요소를 삽입한다.

   * 역순으로 순회하는 이유: 누적합을 사용하기 때문. 이전 요소의 위치를 기억하지 않고 해당 요소의 위치를 바로 구할 수 있음

6. 정렬된 배열을 반환한다.

계수정렬 알고리즘 예시

 

소스코드

public static int[] countingSort(int[] arr) {
    int max = arr[0];
    int min = arr[0];

    // 배열에서 최댓값과 최솟값 찾기
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
        if (arr[i] < min) {
            min = arr[i];
        }
    }

    // 카운트 배열 만들기
    int[] count = new int[max - min + 1];

    // 카운트 배열에 요소별 등장 횟수 저장하기
    for (int i = 0; i < arr.length; i++) {
        count[arr[i] - min]++;
    }

    // 누적합 구하기 (해당 요소가 어떤 인덱스에 위치하는지 결정하는데 사용)
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // 정렬된 배열 만들기
    int[] sortedArr = new int[arr.length];
    for (int i = arr.length - 1; i >= 0; i--) {
        int index = count[arr[i] - min] - 1;
        sortedArr[index] = arr[i];
        count[arr[i] - min]--;
    }

    return sortedArr;
}