기수 정렬 Java 프로그램 및 알고리즘 쉽게 이해하기

기수 정렬(Radix Sort)은 숫자나 문자열을 정렬하는 데 사용되는 비교 기반이 아닌 정렬 알고리즘입니다. 숫자의 각 자리수(1의 자리, 10의 자리, 100의 자리 등)를 기준으로 여러 번 정렬하여 최종적으로 정렬된 결과를 얻습니다. 특정 자리수를 기준으로 정렬하기 때문에 안정 정렬에 속합니다.

---

기수 정렬의 작동 원리

기수 정렬은 숫자를 각 자리수별로 나누어 정렬을 진행합니다. 작은 자리수부터 시작해서 큰 자리수로 넘어가는 방식(가장 낮은 자리수부터 정렬)인 LSD (Least Significant Digit) 방식을 자주 사용합니다.

작동 과정

1. 배열의 가장 작은 자리수(1의 자리)부터 시작합니다.
2. 자리수를 기준으로 숫자를 정렬합니다.
3. 다음 자리수(10의 자리, 100의 자리 등)로 넘어가서 정렬합니다.
4. 가장 큰 자리수까지 반복합니다.
5. 모든 자리수를 기준으로 정렬이 끝나면 결과적으로 배열이 정렬됩니다.

---

예시

정렬할 배열: [170, 45, 75, 90, 802, 24, 2, 66]

1. 1의 자리 정렬: [170, 802, 2, 24, 45, 75, 66, 90]
2. 10의 자리 정렬: [802, 2, 24, 45, 66, 170, 75, 90]
3. 100의 자리 정렬: [2, 24, 45, 66, 75, 90, 170, 802]
   최종 정렬 결과: [2, 24, 45, 66, 75, 90, 170, 802]

---

Java 코드로 구현

아래는 기수 정렬의 간단한 Java 구현입니다:

import java.util.*;

public class RadixSortExample {
    public static void main(String[] args) {
        int[] array = {170, 45, 75, 90, 802, 24, 2, 66};

        System.out.println("정렬 전: " + Arrays.toString(array));
        radixSort(array);
        System.out.println("정렬 후: " + Arrays.toString(array));
    }

    // 기수 정렬 메서드
    public static void radixSort(int[] array) {
        int max = getMax(array); // 배열에서 최대값 찾기
        int place = 1;          // 1의 자리부터 시작

        // 최대 자리수만큼 반복
        while (max / place > 0) {
            countingSort(array, place);
            place *= 10; // 다음 자리수로 이동 (1 -> 10 -> 100 ...)
        }
    }

    // 자리수를 기준으로 한 Counting Sort
    public static void countingSort(int[] array, int place) {
        int n = array.length;
        int[] output = new int[n]; // 정렬된 결과 저장
        int[] count = new int[10]; // 각 자리수(0~9) 카운트 배열

        // 1. 자리수 기준으로 카운트
        for (int i = 0; i < n; i++) {
            int digit = (array[i] / place) % 10;
            count[digit]++;
        }

        // 2. 누적 합 계산
        for (int i = 1; i < 10; i++) {
            count[i] += count[i - 1];
        }

        // 3. 결과 배열에 정렬된 값 저장 (역순으로 처리해서 안정성 유지)
        for (int i = n - 1; i >= 0; i--) {
            int digit = (array[i] / place) % 10;
            output[count[digit] - 1] = array[i];
            count[digit]--;
        }

        // 4. 원본 배열에 결과 복사
        for (int i = 0; i < n; i++) {
            array[i] = output[i];
        }
    }

    // 배열에서 최대값 찾기
    public static int getMax(int[] array) {
        int max = array[0];
        for (int num : array) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }
}

코드 설명

1. getMax 메서드: 배열에서 가장 큰 값을 찾아서 몇 자리수까지 정렬해야 하는지 결정합니다.
2. radixSort 메서드: 각 자리수별로 정렬을 반복합니다. 자리수는 1(1의 자리)에서 시작해 10, 100으로 점점 커집니다.
3. countingSort 메서드:
   • 현재 자리수 기준으로 값을 정렬합니다.
   • 숫자를 자리수로 나눠서 해당 자리의 값(0~9)을 기준으로 카운트 배열에 저장합니다.
   • 누적 합을 계산해 정렬된 위치를 결정합니다.
   • 정렬된 값을 결과 배열에 저장하고 원본 배열로 복사합니다.

---

기수 정렬의 특징

시간 복잡도: O(nk)

• n: 배열의 크기
• k: 숫자의 최대 자리수

1. 공간 복잡도: 추가적인 배열 사용으로 O(n+k)가 필요합니다.
2. 안정 정렬: 값의 순서를 유지합니다(같은 값끼리 위치가 바뀌지 않음).
3. 정렬 조건: 숫자나 고정 길이 문자열에 적합합니다.

---

실행 예시

정렬 전: [170, 45, 75, 90, 802, 24, 2, 66]
정렬 후: [2, 24, 45, 66, 75, 90, 170, 802]

---

이해하기 어려운 부분이 있거나 더 알고 싶은 점이 있으면 알려주세요! 😊