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

15 Dec 2023

java

기수 정렬은 정수를 자릿수 별로 비교하여 정렬하는 알고리즘입니다. 이 알고리즘은 정수의 자릿수를 기준으로 정렬하기 때문에 특히 정수 배열을 정렬하는 데 유용합니다.

기수 정렬 알고리즘 개요

기수 정렬 알고리즘은 일반적으로 다음과 같은 단계로 구성됩니다:

주어진 리스트의 가장 낮은 자릿수부터 가장 높은 자릿수까지 순차적으로 정렬합니다.
각 자릿수에 대해 해당하는 버킷에 값을 넣어 정렬하여 새로운 리스트를 생성합니다.
가장 높은 자릿수까지 정렬을 마칠 때까지 반복합니다.

자바를 이용한 기수 정렬 구현

다음은 자바를 이용한 간단한 기수 정렬의 구현 예시입니다.

import java.util.*;

public class RadixSort {
    public static void radixSort(int[] arr) {
        int max = Arrays.stream(arr).max().getAsInt();
        for (int exp = 1; max / exp > 0; exp *= 10) {
            countingSort(arr, exp);
        }
    }

    private static void countingSort(int[] arr, int exp) {
        int[] output = new int[arr.length];
        int[] count = new int[10];
        Arrays.fill(count, 0);

        for (int value : arr) {
            count[(value / exp) % 10]++;
        }

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

        for (int i = arr.length - 1; i >= 0; i--) {
            output[count[(arr[i] / exp) % 10] - 1] = arr[i];
            count[(arr[i] / exp) % 10]--;
        }

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

    public static void main(String[] args) {
        int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
        radixSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

위의 코드에서 radixSort 메서드는 기수 정렬 알고리즘을 구현하고, countingSort 메서드는 각 자릿수에 대해 카운팅 정렬을 수행합니다.

이 구현을 사용하면 radixSort 메서드를 호출하여 정렬되지 않은 정수 배열을 정렬할 수 있습니다.

결론

자바를 사용하여 기수 정렬을 구현하고 사용하는 방법에 대해 배웠습니다. 기수 정렬은 자릿수 기반의 정렬 알고리즘이므로 특히 정수 배열의 정렬에 효과적입니다.

기수 정렬의 구체적인 구현 방법 및 원리에 대해 더 알고 싶다면 다양한 자료와 책을 참고하는 것이 좋습니다.

자세한 내용은 GeeksforGeeks에서 확인할 수 있습니다.