계수 정렬(Counting Sort)은 숫자의 개수를 세어 정렬하는 알고리즘입니다. 이 알고리즘은 입력 데이터의 크기에 상관없이 일정한 시간 복잡도를 가지며, 비교 기반의 정렬 알고리즘보다 성능이 뛰어납니다. 계수 정렬 알고리즘은 주로 정수 형태의 데이터를 정렬하는데 사용됩니다.

알고리즘 동작 원리

계수 정렬 알고리즘은 다음과 같은 순서로 동작합니다.

1. 입력 데이터의 범위를 파악하여, 카운팅 배열의 크기를 결정합니다.
2. 카운팅 배열을 초기화합니다.
3. 입력 데이터의 각 원소를 카운팅 배열의 인덱스로 사용하여 카운팅 배열의 값을 증가시킵니다.
4. 카운팅 배열의 값을 누적합으로 변경합니다. 이는 정렬된 결과 배열에 각 원소의 위치를 지정하기 위해 사용됩니다.
5. 입력 데이터를 순회하면서, 카운팅 배열을 참조하여 정렬된 결과 배열에 값을 채워 넣습니다.
6. 정렬된 결과 배열을 반환합니다.

Java로 구현한 계수 정렬 알고리즘 예제

public class CountingSort {
    public static void countingSort(int[] arr) {
        int max = 0;
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }

        int[] count = new int[max + 1];
        for (int num : arr) {
            count[num]++;
        }

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

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

        System.arraycopy(sorted, 0, arr, 0, arr.length);
    }

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

위 예제는 Java로 구현한 계수 정렬 알고리즘입니다. 주어진 입력 배열을 계수 정렬 알고리즘을 사용하여 정렬한 후, 결과를 출력하는 예제입니다.

시간 복잡도

계수 정렬 알고리즘의 시간 복잡도는 입력 데이터의 크기에 비례합니다. 입력 데이터의 범위를 K라고 할 때, 계수 정렬 알고리즘의 시간 복잡도는 O(N + K)입니다. 이는 입력 데이터의 크기가 클수록 계수 정렬 알고리즘의 성능이 더욱 빨라짐을 의미합니다.

결론

계수 정렬 알고리즘은 입력 데이터의 크기에 상관없이 일정한 성능을 보장하는 정렬 알고리즘입니다. 특히 정수 형태의 데이터를 정렬할 때 유용하며, 다른 비교 기반의 정렬 알고리즘에 비해 효율적입니다. 다만 입력 데이터의 범위가 크면 메모리를 많이 사용하게 되므로 주의해야 합니다. 계수 정렬 알고리즘은 데이터의 분포를 중요하게 다루는 정렬 알고리즘 중 하나이므로, 데이터 분포를 파악하여 활용할 수 있다면 더욱 효과적으로 사용할 수 있을 것입니다.

참고 자료

• 계수 정렬(Counting Sort) 알고리즘 설명
• 계수 정렬(Counting Sort) 알고리즘 - 위키백과