안녕하세요! 오늘은 기수 정렬(Radix Sort)에 대해 알아보겠습니다. 기수 정렬은 정수나 문자열의 각 자리수를 기준으로 정렬하는 알고리즘으로, 특정 조건 하에 매우 효율적으로 작동합니다. 이 글에서는 기수 정렬의 개념, 동작 방식, 그리고 자바로 구현하는 방법에 대해 설명하겠습니다. 기수 정렬을 통해 알고리즘 문제풀이 능력을 한 단계 끌어올리길 바랍니다.
1. 기수 정렬의 개념
기수 정렬은 대표적인 비교 기반 정렬이 아니라, 비교하지 않고 키의 자리수를 이용하여 정렬하는 비교 비정렬 방식입니다. 일반적으로 기수 정렬은 다음과 같은 주요 단계를 거칩니다:
- 모든 숫자를 자리수 단위로 분리
- LSB(Least Significant Bit)부터 가장 우측 자리수부터 정렬 시작
- 엄격한 정렬이 이루어지도록 자리를 메우기
- 모든 자리수에 대해 반복하여 최종 정렬 완료
기수 정렬의 시간 복잡도는 O(n*k)입니다. 여기서 n은 데이터의 개수, k는 숫자의 자리수입니다. 따라서, 기수 정렬은 자리수가 적은 경우, 또는 데이터의 개수가 많지 않은 경우에 효율적입니다.
2. 기수 정렬의 동작 방식
기수 정렬의 작동 원리를 이해하기 위해 간단한 예제를 통해 설명하겠습니다. 다음 배열을 기수 정렬을 이용해 정렬한다고 가정해 보겠습니다:
[170, 45, 75, 90, 802, 24, 2, 66]이 배열에서 기수 정렬은 다음과 같은 단계로 진행됩니다:
Step 1: LSB(Least Significant Bit) 기준으로 정렬
최하위 자리수(1의 자리)를 기준으로 배열을 정렬합니다:
[170, 90, 802, 24, 2, 45, 75, 66]1의 자리에서 작은 숫자를 먼저 배치하게 됩니다.
Step 2: 10의 자리 기준으로 정렬
이번에는 10의 자리를 기준으로 정렬합니다:
[170, 802, 24, 2, 45, 75, 90, 66]이렇게 한 자리씩 순차적으로 진행해 나갑니다.
Step 3: 100의 자리 기준으로 정렬
마지막으로 100의 자리를 기준으로 정렬하면:
[2, 24, 45, 66, 75, 90, 170, 802]이제 배열이 완전히 정렬된 것을 볼 수 있습니다.
3. 기수 정렬 자바 코드 구현
이제 자바로 기수 정렬을 구현해 보겠습니다. 아래의 코드를 사용하여 기수 정렬을 수행할 수 있습니다:
public class RadixSort {
// 주어진 배열의 최댓값을 찾아 반환하는 메서드
static int getMax(int[] arr, int n) {
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
return max;
}
// 특정 자리수에 대해 counting sort를 수행하는 메서드
static void countingSort(int[] arr, int n, int exp) {
int[] output = new int[n]; // 정렬된 결과를 담을 배열
int[] count = new int[10]; // 0~9까지의 숫자에 대해 카운트
for (int i = 0; i < n; i++) {
count[(arr[i] / exp) % 10]++;
}
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
for (int i = n - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
// 기수 정렬 메서드
static void radixSort(int[] arr) {
int n = arr.length;
int max = getMax(arr, n);
for (int exp = 1; max / exp > 0; exp *= 10) {
countingSort(arr, n, exp);
}
}
// 메인 메서드
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
radixSort(arr);
System.out.println("정렬된 배열: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
이 코드는 숫자의 각 자리별로 정렬을 수행하여 최종적으로 오름차순으로 정렬된 배열을 출력합니다. getMax, countingSort, radixSort 메서드를 통해 각 단계의 역할을 구현하고 있어, 기수 정렬의 작동 원리를 쉽게 이해할 수 있습니다.
4. 기수 정렬의 장단점
장점
- O(n * k)의 시간 복잡도로, 규칙적인 데이터의 정렬에 매우 효율적입니다.
- 접근 패턴이 예측 가능하므로 데이터베이스와 같은 시스템에서 유리합니다.
단점
- 메모리 사용이 추가로 필요하여 큰 데이터셋에는 적합하지 않을 수 있습니다.
- 부동소수점 숫자에는 적용하기 어렵습니다.
5. 기수 정렬 응용 문제
이제 기수 정렬을 활용해볼 수 있는 간단한 문제를 풀어보겠습니다.
문제 설명
정수 배열이 주어질 때, 기수 정렬을 사용하여 배열을 오름차순으로 정렬하라. 단, 배열의 최대 길이는 1000이며, 각 원소는 0 이상 10000 이하의 정수이다.
제한 사항
- 기수 정렬을 반드시 사용해야 하며, 다른 정렬 알고리즘을 사용해서는 안 된다.
- 불필요한 변수를 사용하지 않고도 해결해야 한다.
해결 과정
위의 문제를 해결하기 위해 기수 정렬 알고리즘을 그대로 적용하면 됩니다.
예제 입력
[3, 6, 1, 8, 4, 7, 9, 2, 5]예제 출력
[1, 2, 3, 4, 5, 6, 7, 8, 9]코드 실행
public class RadixSortExample {
public static void main(String[] args) {
int[] arr = {3, 6, 1, 8, 4, 7, 9, 2, 5};
RadixSort.radixSort(arr);
System.out.println("정렬된 배열: ");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
6. 마무리
이번 포스팅에서는 기수 정렬의 개념, 동작 방식, 자바 구현 및 문제 풀이 과정을 다뤄봤습니다. 기수 정렬은 제출 및 제출 기준에 따라 다양한 방법으로 응용될 수 있는 유용한 알고리즘입니다. 알고리즘 문제 풀이에서 기수 정렬을 자주 활용하시길 바라며, 다음에도 유익한 내용을 가지고 찾아오겠습니다. 감사합니다!