Javaでのバケットソート

指定された配列の要素を多数のバケットに分散し、さまざまなソート アルゴリズムを使用するか、バケット ソート アルゴリズムを再帰的に使用して各バケットをソートするソート手法は、Java ではバケット ソートと呼ばれ、空間計算量は O です。 (1)、最悪の場合の複雑さは O(n^2)、最良の場合の複雑さはオメガ(n+k)、平均的な場合の複雑さは theta(n+k) であり、配列の指定された要素を並べ替えるバケット ソート手法は次の速度で機能します。他のソート アルゴリズムと比較して高速であり、バケット ソート アルゴリズムを使用してソートされる配列の要素は均一に分散されている必要があります。

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

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

Java でバケットソートを実行する関数は次のとおりです。

public static int[] bucketsort(int[] array, int maximum_value)
{
int[] newbucket = new int[maximum_value + 1];
int[] sorted_array = new int[array.length];
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}

ここで、array はバケット ソート アルゴリズムを使用してソートされる入力配列、maximum_value は指定された配列に存在する Maximum_value、sorted_array はソートされた要素で構成される結果の配列です。

Java でのバケット ソート アルゴリズムの仕組み

Java でのバケット ソート アルゴリズムの動作は次のとおりです:

• バケットソートアルゴリズムの最初のステップは、バケットとみなされる空の配列を作成することです。
• 2 番目のステップは、要素がソートされる入力配列全体を走査し、各要素をバケットに追加することです。
• 3 番目のステップは、バケット内の各要素を並べ替えることです。
• 4 番目のステップは、バケット内のすべての要素を走査し、それらの要素をそれぞれソートされた順序で元の入力配列に追加することです。

Java でのバケット ソートの例

以下に例を示します:

例 #1

バケット ソート アルゴリズムを実装して指定された配列の要素をソートし、ソートされた配列の要素を画面上の出力として表示する Java プログラム:

コード:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={100, 90, 80, 70, 60, 50, 40, 30, 20, 10};
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

出力:

上記のプログラムでは、バケット配列とみなされる newbucket という空の配列を作成しています。次に、結果の配列を格納するために、sorted_array という別の空の配列を作成します。次に、入力配列を走査して、各要素をバケット配列に追加します。次に、バケット配列内の各要素をソートし、ソートされた各要素を元の入力配列に順番に追加します。次に、バケット ソート手法を使用して指定された配列をソートするために、入力配列の最大値を見つける関数を定義します。次に main 関数が呼び出され、その中で結果の配列が表示されます。出力は上のスナップショットに示されています。

例 #2

バケット ソート アルゴリズムを実装して指定された配列の要素をソートし、ソートされた配列の要素を画面上の出力として表示する Java プログラム:

コード:

import java.util.*;
public class Main
{
public static int[] bucketsort(int[] array, int maximum_value)
{
//creating an empty array called newbucket which is considered as bucket array
int[] newbucket = new int[maximum_value + 1];
//creating another empty array called sorted_array to store the result array
int[] sorted_array = new int[array.length];
//traversing through the input array to add each element to the bucket array
for (int a= 0; a <array.length; a++)
newbucket[array[a]]++;
//sorting each element in the bucket array and adding each sorted element in order to the original input array
int position = 0;
for (int b = 0; b < newbucket.length; b++)
for (int c = 0; c < newbucket[b]; c++)
sorted_array[position++] = b;
return sorted_array;
}
//function to find the maximum value in the input array in order to sort the given array using bucket sort technique
static int maximumValue(int[] array)
{
int maximum_value = 0;
for (int d = 0; d < array.length; d++)
if (array[d] > maximum_value)
maximum_value = array[d];
return maximum_value;
}
//main function is called within which we display the resulting array
public static void main(String args[])
{
int[] array ={ 60, 80, 50, 90, 30, 70, 20 };
int maximum_value = maximumValue(array);
System.out.print("\nThe elements of the array to be sorted are:\n ");
System.out.println(Arrays.toString(array));
System.out.print("\nThe elements of the sorted array sorted using bucket sort algorithm are:\n ");
System.out.println(Arrays.toString(bucketsort(array,maximum_value)));
}
}

出力:

上記のプログラムでは、バケット配列とみなされる新しいバケットと呼ばれる空の配列を作成しています。次に、結果の配列を格納するために、sorted_array という別の空の配列を作成します。次に、入力配列を走査して、各要素をバケット配列に追加します。次に、バケット配列内の各要素をソートし、ソートされた各要素を元の入力配列に順番に追加します。次に、バケット ソート手法を使用して指定された配列をソートするために、入力配列の最大値を見つける関数を定義します。次に main 関数が呼び出され、その中で結果の配列が表示されます。出力は上のスナップショットに示されています。

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