Javaでのバケットソート

1. 前書き

この記事では、* https://en.wikipedia.org/wiki/Bucket_sort [bucket sort]アルゴリズムについて詳しく説明します。* Javaの実装に取り​​組む前に、ちょっとした理論から始めます*ソリューションの単体テストと並行して。 最後に、バケットのソートの*時間の複雑さ*を調べます。

2. バケツ仕分けの理論

バケットソートは、ビンソートとも呼ばれ、特定のソートアルゴリズムです。 ソートは、ソートする要素を個別にソートされた複数のバケットに分散することで機能します。 これにより、要素間の比較の回数を減らし、ソート時間を短縮できます。
バケットのソートを実行するために必要なステップを簡単に見てみましょう*:
  1. 最初に空のバケットの配列を設定します

  2. 適切なバケットに要素を配布します

  3. 各バケットを並べ替える

  4. ソートされたバケットを連結して完全なリストを再作成します

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. 要素の配布

バケットが定義されたので、入力リストの各要素を__hash __method *を使用して関連するバケットに*配布できます:
int max = findMax(initialList);

for (int i : initialList) {
    buckets.get(hash(i, max, numberOfBuckets)).add(i);
}

3.3. 個々のバケットの並べ替え

バケットが定義され、整数でいっぱいになっているので、* _Comparator_を使用してソートします*:
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)time *で完了します。

6. 結論

この記事では、Javaでバケットソートを実装する方法を説明しました。 また、バケットソートアルゴリズムの時間の複雑さも調べました。
いつものように、この記事に示されているコードはhttps://github.com/eugenp/tutorials/tree/master/algorithms-sorting[GitHubで]から入手できます。