자바(Java)로 구현하는 카운팅 정렬(Counting Sort) 프로그램

카운팅 정렬(Counting Sort)이란?

카운팅 정렬은 서로 다른 키 값을 가지는 객체들의 개수를 세어 정렬하는 비교 기반이 아닌 정렬 알고리즘입니다. 각 값의 등장 횟수를 미리 계산해 둔 뒤, 그 정보를 바탕으로 요소들을 올바른 위치에 배치하기 때문에 값의 범위가 제한적일 때 매우 효율적으로 동작합니다.

참고 − 아래 코드는 음수가 포함된 배열에도 그대로 사용할 수 있습니다.

예제 코드

import java.util.*;
public class Demo{
    static void count_sort(int[] arr){
        int max_val = Arrays.stream(arr).max().getAsInt();
        int min_val = Arrays.stream(arr).min().getAsInt();
        int range = max_val - min_val + 1;
        int count[] = new int[range];
        int result[] = new int[arr.length];
        for (int i = 0; i < arr.length; i++){
            count[arr[i] - min_val]++;
        }
        for (int i = 1; i < count.length; i++){
            count[i] += count[i - 1];
        }
        for (int i = arr.length - 1; i >= 0; i--){
            result[count[arr[i] - min_val] - 1] = arr[i];
            count[arr[i] - min_val]--;
        }
        for (int i = 0; i < arr.length; i++){
            arr[i] = result[i];
        }
    }
    static void printVal(int[] arr){
        for (int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println("");
    }
    public static void main(String[] args){
        int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10};
        System.out.println("The array contains");
        for (int i = 0; i < arr.length; i++){
            System.out.print(arr[i] + " ");
        }
        System.out.println();
        System.out.println("Implementing Counting Sort in Java results in : ");
        count_sort(arr);
        printVal(arr);
    }
}

실행 결과

The array contains
-5 0 -3 8 34 56 89 -11 -95 -1 10
Implementing Counting Sort in Java results in :
-95 -11 -5 -3 -1 0 8 10 34 56 89

코드 동작 방식 상세 설명

Demo라는 이름의 클래스에는 핵심 정렬 로직을 담은 'count_sort' 함수가 정의되어 있습니다. 이 함수의 동작 순서는 다음과 같습니다.

먼저 배열을 한 번 순회하면서 각 값의 등장 횟수를 count 배열에 누적합니다. 이때 최솟값(min_val)을 기준으로 인덱스를 조정하기 때문에, 음수가 포함된 배열에서도 오류 없이 동작합니다.

다음으로 count 배열을 순회하며 이전 값을 현재 값에 더해 누적 빈도를 계산합니다. 이 누적값은 각 요소가 정렬된 결과에서 차지할 최종 위치를 나타냅니다.

그런 다음 원본 배열을 역순으로 다시 순회하면서 각 요소를 결과(result) 배열의 올바른 자리에 배치하고, 해당 위치의 count 값을 하나씩 감소시킵니다. 마지막으로 결과 배열의 내용을 원본 배열에 복사하여 정렬을 완료합니다.

이 외에도 콘솔에 배열 데이터를 출력하는 printVal 함수가 정의되어 있으며, main 함수에서는 음수와 양수가 섞인 테스트용 배열을 초기화한 뒤 count_sort를 호출해 실제 정렬 과정을 확인할 수 있습니다.

시간 복잡도

카운팅 정렬의 시간 복잡도는 O(n + k)입니다. 여기서 n은 배열의 길이, k는 최댓값과 최솟값 사이의 범위를 의미합니다. 따라서 데이터 개수 대비 값의 범위가 크지 않은 경우 매우 빠른 성능을 보이지만, 범위가 지나치게 넓다면 메모리 사용량이 커질 수 있다는 점을 유의해야 합니다.