[java] 자바에서 계수 정렬 구현하기

15 Dec 2023

java

계수 정렬(Counting Sort)은 정수를 정렬하는 데 사용되는 비교 기반 정렬 알고리즘입니다. 계수 정렬은 각 요소의 개수를 세고, 그 숫자를 사용하여 정렬된 배열을 생성합니다.

아래는 자바에서 계수 정렬을 구현하는 예제입니다.

public class CountingSort {
    public static void countSort(int[] array, int size) {
        int[] output = new int[size + 1];
        int[] count = new int[256];
        for (int i = 0; i < 256; ++i) {
            count[i] = 0;
        }
        for (int i = 0; i < size; i++) {
            ++count[array[i]];
        }
        for (int i = 1; i <= 255; i++) {
            count[i] += count[i - 1];
        }
        for (int i = size - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            --count[array[i]];
        }
        for (int i = 0; i < size; ++i) {
            array[i] = output[i];
        }
    }
    public static void main(String[] args) {
        int[] array = {4, 2, 2, 8, 3, 3, 1};
        int size = array.length;
        countSort(array, size);
        System.out.println("Sorted array:");
        for (int i = 0; i < size; i++) {
            System.out.print(array[i] + " ");
        }
    }
}

위의 코드에서는 countSort 메서드를 사용하여 계수 정렬을 구현합니다. 주어진 배열의 크기를 기반으로 256개의 카운트 배열을 생성하고, 입력 배열을 반복하여 각 요소의 출현 빈도를 계산합니다. 그런 다음, 누적 카운트를 계산하여 정렬된 순서대로 배열에 배치합니다.

이러한 방식으로 계수 정렬을 통해 정렬된 배열을 얻을 수 있습니다.

위의 자바 코드는 계수 정렬 알고리즘을 구현하는 간단한 예제이며, 실제 활용할 때에는 입력 데이터와 정렬 방식에 맞게 코드를 수정해야 합니다.

더 자세한 내용은 아래 링크를 참고하세요.

계수 정렬 (위키피디아)