[java] 계수 정렬 알고리즘의 최선/최악/평균 시간 복잡도

15 Dec 2023

java

계수 정렬(Counting Sort)은 정렬 알고리즘 중에서 가장 빠른 속도를 자랑하는 알고리즘 중 하나입니다. 이 알고리즘은 정렬 대상의 값 범위가 제한적일 때 사용하기에 적합하며, 주어진 데이터에 대해 특정한 조건이 만족될 때 효과적으로 작동합니다.

최선/최악/평균 시간 복잡도

계수 정렬 알고리즘은 입력값에 비례하는 추가적인 공간을 사용하여 선형 시간 복잡도를 가집니다. 따라서, 최선/최악/평균 시간 복잡도는 O(n + k)로 표현됩니다.

여기서 n은 배열의 크기이고, k는 배열 내 최댓값과 최솟값의 차이입니다.

이 때문에 계수 정렬은 일반적으로 다른 정렬 알고리즘들보다 훨씬 빠르게 동작하는 편입니다.

예시 코드

public class CountingSort {
    public static void countingSort(int[] arr, int maxValue) {
        int[] count = new int[maxValue + 1];
        int[] sortedArr = new int[arr.length];

        for (int i = 0; i < arr.length; i++) {
            count[arr[i]]++;
        }

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

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

        for (int i = 0; i < arr.length; i++) {
            arr[i] = sortedArr[i];
        }
    }
}

계수 정렬 알고리즘의 시간 복잡도에 대한 좀 더 자세한 정보는 Counting Sort - GeeksforGeeks에서 확인할 수 있습니다.