[java] 계수 정렬 알고리즘

14 Dec 2023

java

계수 정렬 알고리즘은 정수 배열을 정렬하는 비교 없는 정렬 알고리즘입니다. 이 알고리즘은 각 숫자의 출현 횟수를 기록하여 정렬을 수행합니다.

알고리즘 설명

0으로 초기화된 크기가 가장 큰 값에 1을 더한 크기의 배열을 생성합니다.
입력 배열을 순회하면서 각 숫자의 출현 횟수를 계산하여 해당 인덱스에 누적합니다.
누적된 값을 이용하여 원본 배열을 순회하면서 정렬된 결과를 새로운 배열에 저장합니다.
새로운 배열을 원본 배열에 복사합니다.

예제 코드

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

        for (int j : arr) {
            count[j - min]++;
        }
        for (int i = 1; i < count.length; i++) {
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i] - min] - 1] = arr[i];
            count[arr[i] - min]--;
        }
        System.arraycopy(output, 0, arr, 0, arr.length);
    }
}

시간 복잡도

계수 정렬은 입력 배열의 크기를 N, 최댓값과 최솟값의 차이를 K라 할 때, 시간 복잡도는 O(N+K)입니다.

결론

계수 정렬 알고리즘은 정수 배열을 정렬하는 데에 효과적인 알고리즘이지만, 입력값의 범위가 매우 크거나 음수가 포함되어 있을 때 유용합니다.

참고 자료

GeeksforGeeks - Counting Sort

내용에 대해 궁금한 점 있으시면 물어보세요!