2

バケットソートの基本的な概念を理解するのに苦労しています。ソートアルゴリズムが何をするのか、O(N) 時間で目的の結果 (内部コンテナのソート) を達成する方法を誰かが正確に説明してくれることを望んでいました。また、これは非常に高速であるように思われるため、他のソート アルゴリズム (バブル、挿入、または選択など) には、バケット ソートよりもそれらを使用するよう説得する利点がありますか?

これは、私がオンラインで見つけたアルゴリズムの実装です。誰かが説明でこれを参照できれば、私はそれを大いに感謝します.

void binsort(std::vector<std::size_t>& A){
    std::vector<std::vector<std::size_t>> B(MAX + 1);
    for(std::size_t i = 0; i < SIZE; ++i){
        B[A[i]].push_back(A[i]);
    }
    std::size_t current = 0;
    for(std::size_t i = 0; i < MAX; ++i){
        for(auto item : B[i]){
            A[current++] = item;
        }
    }
}

助けてくれてありがとう。

4

4 に答える 4

3

この特定の実装について説明してみます。これは、おそらく最も単純なものの 1 つです。偶然ではありませんが、入力ドメインでも許容数の厳しい制限があります (値で表されますMAX)。

10 個の数値のコレクションがあるとします。それらが共有する 1 つの属性は、それらがすべてドメイン [0..5] にあるということです。

{ 3, 2, 2, 5, 1, 4, 0, 2, 5, 4 }

次に、バケットの「リスト」を作成します。各バケットは、ドメインからの値のコレクションを表します。入力配列ではありません。私たちのドメインでは 6 つの可能な値が許可されているため、6 つのバケットを作成します (気付かない場合のために、これらは「順番に」あります)。

 0: {}
 1: {}
 2: {}
 3: {}
 4: {}
 5: {}

次に、入力リストをたどって、各値をバケットにドロップします。概念的には、完成すると次のようになります。

 0: {0}
 1: {1}
 2: {2,2,2}
 3: {3}
 4: {4,4}
 5: {5,5}

次に、バケットのリストを調べて、それぞれの内容を元のコンテナーにダンプし、そこにあった項目を置き換えます。

{ 0, 1, 2, 2, 2, 3, 4, 4, 5, 5}

簡単そうですよね？では、なぜ誰もがあらゆる種類のためにこれを行っていないのでしょうか? さて、問題を拡大して考えてみましょう。可能な値を 6にする代わりにMAX、「値」を1048576(ご参考までに 2 20 ) で境界付けますが、並べ替えられるアイテムの数を 10 に保ちます。

ここで、次のリストが与えられます。

{ 3, 2, 2, 1048576, 1, 4, 0, 2, 5, 4 }

「バケット」リストは次のようになります。

 0: {0}
 1: {1}
 2: {2,2,2}
 3: {3}
 4: {4,4}
 5: {5}
 6: {}
 7: {}
 .....
 1048575: {}
 1048576: {1048576}

ええ、10 個の数字を並べ替えるのに 100 万を超えるバケットが必要です。これは、問題のドメインで許容される最大値であるためです。MAX明らかに、これは大きな天井には適していません。入力範囲を管理可能なセットにサブ分割することは、これに対する実行可能な解決策になります (実際、基本的には基数ソートがどのように機能するかです。

最後の一連の質問に答えるために、入力ドメインがかなり小さい場合、ソート速度でこれを打ち負かすのは難しいでしょう. たとえば、1,000 個の数字のセットがあり、そのすべてが[0..9]. それに数桁追加すると、まったく比較になりません。ただし、支払う価格、重い価格は、制限された入力ドメインです。ドメインのサイズが大きくなるにつれて、バケット分割アルゴリズムの観点からアプローチする必要があり、そうするにつれて、O(NlogN) への道を歩み始めます。それを考えると、考慮に値する独自の警告のセットを持つアルゴリズム (ヒープソート、マージソート、クイックソートなど)がたくさんあります。

明らかに「勝つ」場所: 100 万個の 8 ビット文字 (定義により の値[0..255]) をソートする必要があるとします。それを行うためのより高速なアルゴリズムは見つかりません。ドメインは明確に定義されており、非常に管理しやすく、「バケット」の適切なテーブル (文字通りカウンターのテーブル) が利用されていれば、それに勝るものはありません。

于 2013-02-26T07:52:52.850 に答える
0

与えられた説明はかなりクールです。では、負の数がある場合、そのケースをどのように処理するのでしょうか? これを行う 1 つの方法は、負の数に対して別のバケット リストを保持することです。

このデータセットを想像してください: { -5, -6, 5, 3, 6, -4 }

したがって、ここでの「やりたいことリスト」は次のとおりです。

リスト 1:

0: {0}
1: {0}
2: {0}
3: {1}
4: {0}
5: {1}
6: {1}

やりたいことリスト 2:

-1: {0}
-2: {0}
-3: {0}
-4: {1}
-5: {1}
-6: {1}

したがって、整数のみが含まれる場合は、バケット リストに他のリストを含める必要さえありません。それらは単なるリストにすることができます。

于 2013-03-24T18:25:20.407 に答える
0

これは、ウィキペディアが説明として提供しているものです。これで十分だと思います。

バケット ソート (ビン ソート) は、配列を多数のバケットに分割することによって機能するソート アルゴリズムです。次に、各バケットは、異なるソート アルゴリズムを使用するか、バケット ソート アルゴリズムを再帰的に適用することによって、個別にソートされます。これは分布ソートであり、最上位桁から最下位桁へのフレーバーでの基数ソートのいとこです。バケット ソートは、ピジョンホール ソートを一般化したものです。バケット ソートは比較ソートではないため、Ω(n log n) の下限は適用されません。計算の複雑さの見積もりには、バケットの数が含まれます。

バケットの並べ替えは次のように機能します。

  1. 最初は空の「バケット」の配列を設定します。
  2. Scatter: 元の配列を調べて、各オブジェクトをバケットに入れます。
  3. 空でない各バケットを並べ替えます。
  4. 収集: バケットに順番にアクセスし、すべての要素を元の配列に戻します。
于 2013-02-26T06:38:10.963 に答える