728x90
기수 정렬
비교를 통해 정렬하는 대부분의 알고리즘과는 다르게 숫자를 자릿수 별로 비교하며 정렬하는 비교하며 정렬하는 비교 정렬이 아닌 정렬 알고리즘 입니다. 이 알고리즘은 각 숫자의 자릿수를 기준으로 정렬하며, 작은 단게부터 시작하여 큰 단계까지 반복적으로 수행합니다. 또한 일반적으로 가장 낮은 자리수부터 시작하여 가장 높은 자리수까지 정렬합니다. 각 자릿수를 기준으로 숫자를 정렬하는 과정에서 카운팅 정렬이 사용될 수 있습니다.
각 숫자의 1의 자리를 기준으로 정렬하고 10의 자리를 기준으로 추가적으로 정렬합니다. 이 때 10의 자리 숫자가 같을 때는 1의 자리 숫자가 작은 순서로 배치합니다. 중복된 숫자가 있다면, 정렬된 후에도 중복된 순서가 입력 순서와 같다면 안정적이다. 또한 안정적인 정렬 알고리즘은 중복된 숫자의 상대적인 순서가 보존되므로, 그 순서가 정렬 전과 정렬 후에 동일 하게 유지됩니다. 만약 중복된 숫자의 순서가 정렬 후에 변경된다면 해당 알고리즘은 불안정적 이라고 할 수 있습니다.
LSD
가장 낮은 자릿수부터 비교하여 정렬
- 일반적으로 0부터 9까지의 숫잘를 기준으로 정렬합니다.
- 모든 숫자를 해당 자릿수를 기준으로 비교하여 재배열합니다.
MSD
다음 높은 자릿수로 이동하여 정렬 작업 반복
- 가장 낮은 자릿수부터 가장 높은 자릿수까지 위의 과정을 반복합니다.
- 이 과정을 마치면 숫자들은 모든 자릿수에 대한 올바른 순서로 정렬됩니다.
특징
기수 정렬은 숫자 자릿수를 이용하여 정렬하기 때문에 숫자를 비교하는 대신 자릿수를 기준으로 정렬합니다.
안정적인 정렬 : 동일한 값에 대해 순서가 변경되지 않기 때문에 안정적인 정렬 알고리즘입니다.
가장 낮은 자릿수부터 가장 높은 자릿수까지 차례로 정렬하며, 이를 반복하여 숫자들을 정렬합니다.
장점
- 일정 범위 내의 숫자들에 대해 빠르고 효율적인 알고리즘
- 동일값에 대한 순서가 바뀌지 않아 안정적인 정렬을 제공합니다.
단점
- 정렬한 숫자들의 자릿수에 따라 메모리 요구량이 늘어날 수 있습니다.
기수 정렬 코드
import java.util.Arrays;
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) {
countSort(arr, exp);
}
}
// Counting Sort를 이용하여 각 자릿수별로 정렬하는 함수
private static void countSort(int[] arr, int exp) {
int[] output = new int[arr.length];
int[] count = new int[10]; // 0부터 9까지의 숫자를 세기 위한 배열
// 각 숫자의 개수 count
for (int i = 0; i < arr.length; i++) {
count[(arr[i] / exp) % 10]++;
}
// count 배열 업데이트: 누적 count로 변경
for (int i = 1; i < 10; i++) {
count[i] += count[i - 1];
}
// output 배열에 정렬된 숫자 배치
for (int i = arr.length - 1; i >= 0; i--) {
output[count[(arr[i] / exp) % 10] - 1] = arr[i];
count[(arr[i] / exp) % 10]--;
}
// output 배열을 arr로 복사
System.arraycopy(output, 0, arr, 0, arr.length);
}
// 결과 확인을 위한 출력 함수
public static void printArray(int[] arr) {
System.out.println(Arrays.toString(arr));
}
// 테스트를 위한 메인 함수
public static void main(String[] args) {
int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};
System.out.println("기수 정렬 전 배열:");
printArray(arr);
radixSort(arr);
System.out.println("기수 정렬 후 배열:");
printArray(arr);
}
}
728x90