[java] 계수 정렬 알고리즘의 동작 원리

15 Dec 2023

java

계수 정렬은 정수 배열을 정렬하는 비교 기반 정렬 알고리즘이다. 이 알고리즘은 비교를 사용하지 않고 정렬을 수행하기 때문에 시간 복잡도를 줄일 수 있다.

동작 원리

각 원소의 출현 빈도를 센다.
누적 빈도 배열을 생성하고 각 요소의 누적 빈도를 계산한다.
원본 배열을 반대로 순회하면서 누적 빈도 배열을 참조하여 적절한 위치에 요소를 배치한다.
처리한 요소의 누적 빈도를 감소시킨다.
원본 배열 순회가 끝날 때까지 3~4단계를 반복한다.

시간 복잡도

계수 정렬 알고리즘의 시간 복잡도는 O(n+k)이다. 이 때 n은 원소의 개수, k는 숫자의 최대값이다.

이 알고리즘은 비교를 하지 않고 원소의 출현 빈도로 정렬하기 때문에 숫자의 범위가 작은 경우에 매우 효율적이다.

예시 코드

아래는 Java로 구현한 계수 정렬 알고리즘의 예시이다.

public class CountingSort {
    public static void countingSort(int[] array, int range) {
        int[] count = new int[range + 1];
        int[] output = new int[array.length];

        for (int value : array) {
            count[value]++;
        }

        for (int i = 1; i <= range; i++) {
            count[i] += count[i - 1];
        }

        for (int i = array.length - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        System.arraycopy(output, 0, array, 0, array.length);
    }
}

결론

계수 정렬은 숫자의 범위가 작을 때 효율적으로 사용할 수 있는 정렬 알고리즘이다. 출현 빈도를 이용하여 원소를 정렬하기 때문에 시간 복잡도가 매우 낮다.

참고 문헌:

Introduction to Algorithms, 3rd Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein