[java] 계수 정렬 알고리즘

15 Dec 2023

java

계수 정렬은 정렬 알고리즘 중 하나로, 일반적으로 정수 형태의 데이터를 정렬하는 데 사용됩니다. 이 알고리즘은 비교 정렬 알고리즘과 달리 비교를 통해 요소를 정렬하지 않으며, 데이터의 특정 범위에 대한 빈도수를 계산하여 정렬을 수행합니다.

알고리즘 동작 방식

가장 큰 값 찾기: 정렬할 데이터 중 가장 큰 값의 크기를 구합니다.
빈도수 계산: 0부터 최대값까지의 빈도수를 기록할 임시 배열을 생성하고, 각 값의 빈도수를 계산합니다.
누적 빈도수 계산: 각 값의 누적 빈도수를 계산합니다.
정렬 배열 구성: 누적 빈도수를 이용하여 정렬된 배열을 구성합니다.

예시 코드

public class CountingSort {
    void sort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        int[] count = new int[max + 1];
        int[] output = new int[arr.length];

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

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

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

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

계수 정렬은 데이터 범위가 크지 않을 때, 또한 데이터가 정수 형태일 때 가장 효율적으로 동작합니다. 그러나 데이터의 범위가 매우 크고 실수 형태일 경우에는 추가적인 고려가 필요합니다.

이는 안정 정렬(Stable sort)이며, 시간 복잡도는 O(n+k)입니다. 여기서 k는 데이터의 최대값에 해당하는 범위를 의미합니다.

알고리즘 동작 방식

예시 코드

참고 자료