基数ソート Java

Java の基数ソートは、整数キーを使用し、同じ有効位置と位の値を共有する個々の数字でキーをグループ化する整数ソート アルゴリズムです。次に、要素は昇順/降順にソートされます。基数ソートの主な考え方は、最下位桁から最上位桁まで順番に桁ごとにソートを実行することです。カウンティングソートをサブルーチンとして使用して、数値の配列をソートします。基数ソートにはカウントソートが組み込まれているため、アルゴリズムがソートするキーの範囲を増やして効率を低下させることなく、大きな数字や複数の桁をソートできます。基数ソートをさらに深く掘り下げて、Java で基数ソートがどのように機能するかをいくつかの例とともに見てみましょう。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

構文

基数ソートには、アルゴリズムのステップまたはソートの実行方法に関するフローチャートが含まれています。それでは、基数ソートのアルゴリズムを見てみましょう。

基数ソートのアルゴリズム

ステップ 1: まず、配列内の最大の要素、つまり最大要素を見つける必要があります。そして、X を最大要素の桁数として考えます。

最大要素の位の値を調べる必要があるため、X を計算する必要があります。

ステップ 2: 次に、最大要素の各位の値を調べる必要があります。

ステップ 3: 安定した並べ替えアルゴリズムを使用して、各有効桁値で数字を並べ替える必要があります。

ステップ 4: 要素は単位位の値 {X=0}

の桁に基づいて並べ替えられるようになりました。

ステップ 5: 次に、要素を 10 の位の数字に基づいて並べ替えます {X=10}

ステップ 6: 次に、百の位 {X=100}

の桁に基づいて要素を並べ替えます。

ステップ 7: 配列内の要素の値を配置する場合、つまり X 値に基づいて、上記のステップを繰り返します。

Java では基数ソートはどのように実行されますか?

基数ソートがどのように実装されるかをいくつかの例で確認してみましょう。

例 #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]+" ");
}
}

出力:

ここでは、入力配列が基数ソートとカウントソートを使用してソートされていることがわかります。

例 #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));
}
}

出力:

ここでは、基数ソートを使用して入力配列をソートするために別のロジックを使用しています。

それでは、実際の例を使用して基数ソートがどのように行われるかを説明します。

入力配列を [72, 15, 30, 21, 13, 944, 417] とします。

ステップ 1: 配列から最大値、つまり 944 を取得します。したがって、X 値は 3、つまり X = no になります。最大要素の桁数。実際には、配列の配置が 3 回行われることを意味します

ステップ 2: そこで、最下位桁に基づいて数値を並べてみます。

すべての要素の単位の値を考慮して、配列を以下のように再配置します。

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

すべての要素の十の位の値を考慮して、配列を以下のように並べ替えます。

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

すべての要素の百の位の値があればそれを考慮して、配列は以下のように再配置されます。

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

ステップ 3: これで配列がソートされました。

結論

これで、「Java での基数ソート」の記事を終了します。基数ソートとは何か、およびカウンティング ソートを使用して基数ソートがどのように実装されるかを見てきました。これはソートの最も単純な形式の 1 つであり、キーが短い場合、つまり要素の範囲が狭い場合には高速になります。過去数年間、ソート技術は日常的なアルゴリズムの使用に広く導入されてきました。ただし、いくつかの欠点もあります。基数ソートは入力 (文字や数字など) に大きく依存するため、他のソートよりも柔軟性が低くなります。

以上が基数ソート Javaの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。