카운팅 정렬(Counting Sort)

개요

• 정수 정렬 알고리즘 : 정수 key에 따라 객체를 수집하는 것
• 정수의 개수를 세는 방식으로 동작

특징

• 시간복잡도 : $O(n + k)$ ($k$ is the range of non-neg key values)
• 공간복잡도 : $O(n + k)$
• 정수의 범위가 제한적일 때 가장 효율적으로 작동한다.

구현

import java.util.Arrays;

public class CountingSort {
    public static void main(String[] args) {
        int[] arr = {77, 32, 37, 17, 22, 8, 13, 42, 26};
        // 배열의 최솟값과 최댓값 찾기
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int num : arr) {
            min = Math.min(min, num);
            max = Math.max(max, num);
        }

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

        // 각 정수의 개수 세기
        for (int num : arr) {
            count[num - 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 num = arr[i];
            int index = count[num - min] - 1; // 정렬된 배열에서의 인덱스

            sortedArr[index] = num;
            count[num - min]--; // 해당 정수의 개수 감소
        }

        System.out.println(Arrays.toString(sortedArr));
    }
}