Javaでのバケットソート
1. 序章
この記事では、
2. バケットソートの理論
バケットソートは、ビンソートとも呼ばれ、特定のソートアルゴリズムです。 並べ替えは、並べ替える要素をいくつかの個別に並べ替えられたバケットに分散することで機能します。 これにより、要素間の比較回数を減らし、並べ替え時間を短縮することができます。
バケットソートを実行するために必要なステップを簡単に見てみましょう。
- 最初は空だったバケットの配列を設定します
- 要素を適切なバケットに配布します
- 各バケットを並べ替える
- ソートされたバケットを連結して、完全なリストを再作成します
3. Javaの実装
このアルゴリズムは言語固有ではありませんが、Javaでソートを実装します。 上記のリストを段階的に調べて、整数のリストをソートするコードを書いてみましょう。
3.1. バケットの設定
まず、ハッシュアルゴリズムを決定して、どの要素をどのバケットに配置するかを決定する必要があります。
private int hash(int i, int max, int numberOfBuckets) {
return (int) ((double) i / max * (numberOfBuckets - 1));
}
ハッシュメソッドを定義すると、入力リストサイズの平方根としてビンの数を指定できます。
final int numberOfBuckets = (int) Math.sqrt(initialList.size());
List<List<Integer>> buckets = new ArrayList<>(numberOfBuckets);
for(int i = 0; i < numberOfBuckets; i++) {
buckets.add(new ArrayList<>());
}
最後に、入力リストの最大整数を決定するための短いメソッドが必要です。
private int findMax(List<Integer> input) {
int m = Integer.MIN_VALUE;
for (int i : input) {
m = Math.max(i, m);
}
return m;
}
3.2. 要素の配布
バケットが定義されたので、ハッシュメソッドを使用して、入力リストの各要素を関連するバケットに配布できます。
int max = findMax(initialList);
for (int i : initialList) {
buckets.get(hash(i, max, numberOfBuckets)).add(i);
}
3.3. 個々のバケットの並べ替え
バケットが定義され、整数でいっぱいになったら、コンパレータを使用してバケットを並べ替えましょう:
Comparator<Integer> comparator = Comparator.naturalOrder();
for(List<Integer> bucket : buckets){
bucket.sort(comparator);
}
3.4. バケットの連結
最後に、バケットをまとめて単一のリストを再作成する必要があります。 バケットは並べ替えられているため、各バケットを1回ループして、要素をマスターリストに追加するだけで済みます。
List<Integer> sortedArray = new LinkedList<>();
for(List<Integer> bucket : buckets) {
sortedArray.addAll(bucket);
}
return sortedArray;
4. コードのテスト
実装が完了したら、期待どおりに機能することを確認するための簡単な単体テストを作成しましょう。
BucketSorter sorter = new IntegerBucketSorter();
List<Integer> unsorted = Arrays.asList(80,50,60,30,20,10,70,0,40,500,600,602,200,15);
List<Integer> expected = Arrays.asList(0,10,15,20,30,40,50,60,70,80,200,500,600,602);
List<Integer> sorted = sorter.sort(unsorted);
assertEquals(expected, sorted);
5. 時間計算量
次に、バケットソートを実行する時間の複雑さを簡単に見てみましょう。
5.1. 最悪のシナリオ
最悪のシナリオでは、すべての要素が同じバケット内で逆の順序で検出されます。この場合、バケットの並べ替えを、すべての要素が含まれる単純な並べ替えに減らします。は他のすべての要素と比較され、はO(n²)の時間計算量をもたらします。
5.2. 平均的なケースシナリオ
平均的なケースでは、要素が入力バケット間で比較的均等に分散されていることがわかります。各ステップで入力バケットを1回繰り返すだけでよいため、バケットソートは次のように完了します。 O(n)時間。
6. 結論
この記事では、Javaでバケットソートを実装する方法を見ました。 また、バケットソートアルゴリズムの時間計算量も調べました。
いつものように、この記事に示されているコードは、GitHubでから入手できます。