[정렬] 계수 정렬 : Counting Sort

 

📌 계수 정렬 : Counting Sort

✅ 데이터의 각 값이 등장하는 횟수를 카운트하여, 그 횟수를 기반으로 데이터를 정렬

✅ 이때, 데이터를 정렬하고자 하는 범위가 정해져 있어야 한다.

✅ 시간 복잡도 :   \(O(n + k)\)

✅ 데이터 값의 범위가 제한적이면 매우 빠르게 동작하나, 데이터 범위가 크면 매우 비효율 적이다.

import java.util.Arrays;

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

    private static void countingSort(int[] arr){
        int max = getMax(arr);
        int[] count = new int[max + 1];

        //각 숫자 등장 횟수 카운트
        for(int num : arr){
            count[num]++;
        }

        //빈도 배열을 원본 배열에 반영
        int index = 0;
        for(int i = 0; i < count.length; i++){
            while(count[i]-- > 0){
                arr[index++] = i;
            }
        }
    }

    private static int getMax(int[] arr){
        int max = arr[0];
        for(int num : arr){
            if(max < num){
                max = num;
            }
        }
        return max;
    }
}

 

 

---

계수 정렬의 과정