고급 정렬 알고리즘 구현: 카운팅 정렬 (Java)

카운팅 정렬

카운팅 정렬

- 비교 기반 정렬이 아니라 데이터의 개수를 세어서 정렬하는 방식

- 데이터의 최대값(K)를 알아야 함

- 데이터가 음수가 포함되면 사용하기 어렵거나 추가적인 조치 필요

- 안정 정렬

 

시간 복잡도

최선, 평균, 최악 : O(N+K)

 

 

단점

실수 정렬 불가능

음수가 포함되면 추가적인 조치 필요

최대값(K)이 너무 크면 비효율적(메모리 사용 증가)

 

코드(오름차순)

import java.util.Arrays;

public class CountingSort {

    public static void countingSort(int[] arr) {

        // 최댓값 찾기
        int max = Arrays.stream(arr).max().getAsInt();

        // 카운트 배열 (0 ~ max)
        int[] count = new int[max+1];

        // 1. 각 숫자의 개수를 세기
        for(int num: arr) {
            count[num]++;
        }

        // 2. 누적합으로 변환하여 정렬된 위치를 결정
        for(int i = 1; i <= max; i++){
            count[i] += count[i-1];
        }

        // 3. 정렬된 배열으 만들기(역순으로 처리하여 안정 정렬 유지)
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[arr[i]] - 1] = arr[i];
            count[arr[i]]--;  // 같은 숫자가 들어갈 위치를 조정
        }

        // 4. 원본 배열에 정렬된 값 복사
        System.arraycopy(output, 0, arr, 0, arr.length);

    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1};
        countingSort(arr);
        System.out.println(Arrays.toString(arr));
    }

}