기수 정렬 Java

Java의 기수 정렬은 정수 키를 사용하고 동일한 유효 위치와 자릿값을 공유하는 개별 숫자로 키를 그룹화하는 정수 정렬 알고리즘입니다. 그런 다음 요소는 증가/감소 순서에 따라 정렬됩니다. 기수 정렬의 주요 아이디어는 최하위 숫자부터 최상위 숫자까지 숫자별로 정렬을 수행하는 것입니다. counting sort를 서브루틴으로 사용하여 숫자 배열을 정렬합니다. 기수 정렬에는 계산 정렬이 통합되어 있어 알고리즘이 정렬하는 키 범위를 늘려 효율성을 떨어뜨리지 않고도 크고 여러 자리를 정렬할 수 있습니다. Radix 정렬에 대해 더 자세히 알아보고 몇 가지 예를 통해 Java에서 Radix 정렬이 작동하는 방식을 살펴보겠습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

구문

기수 정렬에는 정렬 수행 방법에 대한 알고리즘 단계 또는 흐름도가 있습니다. 그럼 기수 정렬 알고리즘을 살펴보겠습니다.

기수 정렬 알고리즘

1단계: 먼저 배열에서 가장 큰 요소, 즉 max 요소를 찾아야 합니다. 그리고 X를 최대요소의 자릿수로 생각해보자.

최대 요소의 자리값을 거쳐야 하므로 X를 계산해야 합니다.

2단계: 이제 최대 요소의 각 자리값을 살펴보아야 합니다.

3단계: 각 유효 자릿수에서 숫자를 정렬하려면 안정적인 정렬 알고리즘을 사용해야 합니다.

4단계: 이제 요소는 단위 자릿값 {X=0}의 숫자를 기준으로 정렬됩니다.

5단계: 그런 다음 십의 자리 {X=10}를 기준으로 요소를 정렬합니다

6단계: 그런 다음 백의 자리 {X=100}

에서 숫자를 기준으로 요소를 정렬합니다.

7단계: 배열의 요소에 대한 자릿값이 더 있으면(예: X 값 기준) 위 단계가 반복됩니다.

Java에서는 기수 정렬이 어떻게 수행되나요?

예제를 통해 Radix 정렬이 어떻게 구현되는지 확인해 보겠습니다.

예시 #1

코드:

import java.util.*;
public class radixSorting {
static int get_maxVal(int radixArr[], int arrLen) {
int maxVal = radixArr[0];
for (int i = 1; i < arrLen; i++)
if (radixArr[i] > maxVal)
maxVal = radixArr[i];
return maxVal;
}
static void countSorting(int radixArr[], int arrLen, int exp) {
int resultArray[] = new int[arrLen];
int i;
int countVal[] = new int[10];
Arrays.fill(countVal,0);
for (i = 0; i < arrLen; i++)
countVal[ (radixArr[i]/exp)%10 ]++;
for (i = 1; i < 10; i++)
countVal[i] += countVal[i - 1];
for (i = arrLen - 1; i >= 0; i--) {
resultArray[countVal[ (radixArr[i]/exp)%10 ] - 1] = radixArr[i];
countVal[ (radixArr[i]/exp)%10 ]--;
}
for (i = 0; i < arrLen; i++)
radixArr[i] = resultArray[i];
}
static void radix_array_sort(int radixArr[], int arrLen) {
int m = get_maxVal(radixArr, arrLen);
for(int exp = 1; m/exp > 0; exp *= 10)
countSorting(radixArr, arrLen, exp);
}
public static void main (String[] args) {
int radixArr[] = {32,456,71,10,9,892,55,90,23,667};
int arrLen = radixArr.length;
System.out.println("Array after radix sort is ");
radix_array_sort(radixArr, arrLen);
for (int i=0; i<arrLen; i++)
System.out.print(radixArr[i]+" ");
}
}

출력:

여기서는 Counting 정렬과 함께 Radix 정렬을 사용하여 입력 배열이 정렬된 것을 볼 수 있습니다.

예시 #2

코드:

import java.util.Arrays;
public class RadixSorting {
public static void sorting(int[] inputArray) {
RadixSorting.sorting(inputArray, 10);
}
public static void sorting(int[] inputArray, int radix) {
if (inputArray.length == 0) {
return;
}
int minVal = inputArray[0];
int maxVal = inputArray[0];
for (int i = 1; i < inputArray.length; i++) {
if (inputArray[i] < minVal) {
minVal = inputArray[i];
} else if (inputArray[i] > maxVal) {
maxVal = inputArray[i];
}
}
int exponentVal = 1;
while ((maxVal - minVal) / exponentVal >= 1) {
RadixSorting.countingSort_by_digit(inputArray, radix, exponentVal, minVal);
exponentVal *= radix;
}
}
private static void countingSort_by_digit(
int[] inputArray, int radix, int exponentVal, int minVal) {
int bucket_index;
int[] bucket = new int[radix];
int[] output = new int[inputArray.length];
for (int i = 0; i < radix; i++) {
bucket[i] = 0;
}
for (int i = 0; i < inputArray.length; i++) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
bucket[bucket_index]++;
}
for (int i = 1; i < radix; i++) {
bucket[i] += bucket[i - 1];
}
for (int i = inputArray.length - 1; i >= 0; i--) {
bucket_index = (int)(((inputArray[i] - minVal) / exponentVal) % radix);
output[--bucket[bucket_index]] = inputArray[i];
}
for (int i = 0; i < inputArray.length; i++) {
inputArray[i] = output[i];
}
}
public static void main(String args[])
{
RadixSorting rs = new RadixSorting();
int radix_input[] = {72, 15, 30, 21, 13, 944, 417};
System.out.println("Original Input Array:");
System.out.println(Arrays.toString(radix_input));
rs.sorting(radix_input);
System.out.println("Sorted Array using Radix Sort:");
System.out.println(Arrays.toString(radix_input));
}
}

출력:

여기에서는 Radix Sort를 사용하여 입력 배열을 정렬하기 위해 다른 논리를 사용하고 있습니다.

이제 라이브 예제를 통해 Radix 정렬이 어떻게 수행되는지 설명하거나 보여드리겠습니다.

입력 배열을 [72, 15, 30, 21, 13, 944, 417]로 간주합니다.

1단계: 배열에서 최대값(예: 944)을 가져옵니다. 따라서 이제 X 값은 3, 즉 X = no가 됩니다. 이는 실제로 배열 배열이 세 번 완료됨을 의미합니다

2단계: 이제 최하위 숫자를 기준으로 숫자를 배열해 보겠습니다.

모든 요소의 단위 자리값을 고려하면 아래와 같이 배열이 재배열됩니다.

[30, 21, 72, 13, 944, 15, 417]

모든 요소의 10자리 값을 고려하면 아래와 같이 배열이 재정렬됩니다.

[13, 15, 417, 21, 30, 944, 72]

모든 요소의 백 자리 값을 고려하면 아래와 같이 배열이 재배열됩니다.

[13, 15, 21, 30, 72, 417, 944]

3단계: 배열이 정렬되었습니다.

결론

이상으로 'Java의 기수 정렬'에 대한 글을 마치겠습니다. 지금까지 기수 정렬이 무엇인지, 계수 정렬을 사용하여 어떻게 구현되는지 살펴보았습니다. 이는 가장 간단한 정렬 형식 중 하나이며 키가 짧은 경우, 즉 요소 범위가 적은 경우 더 빠릅니다. 지난 몇 년 동안 정렬 기술은 일상적인 알고리즘 사용에 광범위하게 적용되었습니다. 그러나 몇 가지 단점도 있습니다. 기수 정렬은 입력(예: 문자 또는 숫자)에 크게 의존하므로 다른 정렬보다 유연성이 떨어집니다.

위 내용은 기수 정렬 Java의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!