バケットソート – 日本語百科事典辞書

Bucket_sort

は、バケットごとに複数のキーを許可するバケットソートのバリエーションについて説明しています。バケットごとに1つのキーを使用するバリエーションについては、鳩の巣ソートを参照してください
バケットソート、またはビンソートは、配列の要素をいくつかのバケットに分散することによって機能するソートアルゴリズムです。次に、各バケットは、異なるソートアルゴリズムを使用するか、バケットソートアルゴリズムを再帰的に適用することにより、個別にソートされます。これは、鳩の巣ソートの一般化である分布ソートであり、最上位から最下位の有効数字フレーバーの基数ソートのいとこです。バケットソートは比較を使用して実装できるため、比較ソートアルゴリズムと見なすこともできます。計算の複雑各バケットの並べ替えに使用されるアルゴリズム、使用するバケットの数、および入力が均一に分散されているかどうかによって異なります。
バケットソート
クラス
ソートアルゴリズム
データ構造
配列
最悪の場合のパフォーマンス O （（ログ（（）。）。 {O left（n log（n） right）}
平均パフォーマンス O （（ + 2k + k ）。 {O left（n + { frac {n ^ {2}} {k}} + k right）}
、ここで、kはバケットの数です。 O （（）。いつ k ≈ {O（n）、{ text {when}} k approx n} 最悪の場合のスペースの複雑さ O （（ + k ）。
{O（n + k）}
要素はビンに分散されます
次に、要素は各ビン内で並べ替えられます
バケットソートは次のように機能します。
最初は空の「バケット」の配列を設定します。
スキャッター：元の配列を調べて、各オブジェクトをバケットに入れます。
空でない各バケットを並べ替えます。
収集：バケットに順番にアクセスし、すべての要素を元の配列に戻します。

コンテンツ
1 擬似コード
2 分析
2.1 最悪の場合の分析 2.2 平均的なケースの分析
3 最適化
4 バリアント
4.1 一般的なバケットソート 4.2 ProxmapSort 4.3 ヒストグラムの並べ替え 4.4 郵便配達員の種類 4.5 シャッフルソート
5 他のソートアルゴリズムとの比較
6 参考文献
7 外部リンク

擬似コード
関数bucketSort（array、k）はバケットk個の空のリストの新しい配列 M配列内の最大キー値 for i = 1 to length（array）do array をバケットに
挿入します[floor（k×array / M）] for i = 1 to k do
nextSort（バケット）バケット、….、バケットの連結を返します
配列がソートされる配列を示し、kが使用するバケットの数を示すとします。すべてのキーを1回繰り返すことで、最大キー値の線形時間を計算できます。フロア関数は、整数に浮動番号を変換するために使用される（そしておそらく余りにデータ型鋳造）されなければなりません。関数nextSortは、各バケットを並べ替えるために使用される並べ替え関数です。従来は挿入ソートが使用されていましたが、選択ソートやマージソートなどの他のアルゴリズムも使用できます。使用バケットソートとしての地位をnextSortが相対生成基数ソート。特に、n = 2の場合はクイックソートに対応します（ただし、ピボットの選択が不十分になる可能性があります）。

分析

最悪の場合の分析
入力に互いに近い複数のキーが含まれている場合（クラスタリング）、それらの要素は同じバケットに配置される可能性が高く、その結果、一部のバケットには平均よりも多くの要素が含まれます。最悪のシナリオは、すべての要素が1つのバケットに配置されている場合に発生します。全体的なパフォーマンスは、たとえば、各バケットの並べ替えに使用されるアルゴリズムによって支配されます。 O （（ 2）。
{O（n ^ {2}）}
$O(n^{2})""$
挿入ソートまたは O （（ログ
（（）。）。 {O（n log（n））}

マージソートなどの比較ソートアルゴリズム。

平均的なケースの分析
入力が均一に分布している場合を考えてみましょう。バケットを初期化し、配列内の最大キー値を見つける最初のステップは、次の方法で実行できます。 O （（）。
{O（n）}

時間。除算と乗算を一定時間で実行できる場合、各要素をバケットに分散することにもコストがかかります O （（）。
{O（n）}

。挿入ソートを使用して各バケットをソートすると仮定すると、3番目のステップのコスト O （（ ∑
I= 1 k私 2 ）。
{O（ textstyle sum _ {i = 1} ^ {k} n_ {i} ^ {2}）}

、どこ私
{n_ {i}}

インデックス付けされたバケットの長さです I {i}

。平均時間についてですので、期待 E （（私
2）。
{E（n_ {i} ^ {2}）}

代わりに評価する必要がさせて I {X_ {ij}}

である確率変数である 1 {1}

要素の場合 {j}

バケツに入れられます I {i}

、と 0 {0}

それ以外は。我々は持っています私 = ∑ =
1 I {n_ {i} = sum _ {j = 1} ^ {n} X_ {ij}}

。したがって、 E （（私 2 ）。= E（（ ∑ =
1 I ∑
k = 1 私 k ）。= E（（ ∑ =
1 ∑
k = 1 I 私 k ）。= E（（ ∑ =
1 I 2
）。+ E（（ ∑ 1 ≤ 、 k ≤ ∑ ≠
k I 私 k ）。
{{ begin {aligned} E（n_ {i} ^ {2}）＆= E left（ sum _ {j = 1} ^ {n} X_ {ij} sum _ {k = 1} ^ {n} X_ {ik} right）\＆= E left（ sum _ {j = 1} ^ {n} sum _ {k = 1} ^ {n} X_ {ij} X_ {ik } right）\＆= E left（ sum _ {j = 1} ^ {n} X_ {ij} ^ {2} right）+ E left（ sum _ {1 leq j、k leq n} sum _ {j neq k} X_ {ij} X_ {ik} right） end {aligned}}}
最後の行は、合計をケースに分けています = k {j = k}

とケース ≠ k {j neq k}

。オブジェクトがバケットに配布される可能性があるため I {i}

は1 / k
{1 / k}

、 I {X_ {ij}}

確率で1です1 / k
{1 / k}

それ以外の場合は0。 E （（ I 2 ）。 =1 2 ⋅ （（ 1 k ）。 0 2 ⋅ （（ 1− 1 k
）。 1 k {E（X_ {ij} ^ {2}）= 1 ^ {2} cdot left（{ frac {1} {k}} right）+ 0 ^ {2} cdot left（1 -{ frac {1} {k}} right）= { frac {1} {k}}}

E （（ I 私 k ）。= 1 ⋅（（ 1 k ）。（（ 1 k ）。 1 2
{E（X_ {ij} X_ {ik}）= 1 cdot left（{ frac {1} {k}} right） left（{ frac {1} {k}} right） = { frac {1} {k ^ {2}}}}
合計すると、 E （（ ∑ =
1 I 2 ）。 + E （（ ∑ 1 ≤ 、 k ≤ ∑ ≠
k I 私 k ）。= ⋅1 k+ （（ − 1 ）。
⋅1 2= 2+ k−k 2
{E left（ sum _ {j = 1} ^ {n} X_ {ij} ^ {2} right）+ E left（ sum _ {1 leq j、k leq n} 合計_ {j neq k} X_ {ij} X_ {ik} right）= n cdot { frac {1} {k}} + n（n-1） cdot { frac {1} {k ^ {2}}} = { frac {n ^ {2} + nk-n} {k ^ {2}}}}
最後に、複雑さは次のようになります O （（ ∑ I =1 E （（私 2 ）。）。= O（（ ∑I = 1 2+ k
− k 2 ）。= O（（ 2k +
NS）。
{O left（ sum _ {i = 1} ^ {k} E（n_ {i} ^ {2}） right）= O left（ sum _ {i = 1} ^ {k} { frac {n ^ {2} + nk-n} {k ^ {2}}} right）= O left（{ frac {n ^ {2}} {k}} + n right）}

。
バケットソートの最後のステップは、各バケット内のソートされたすべてのオブジェクトを連結することであり、 O （（ k ）。 {O（k）}

時間。したがって、全体の複雑さは O （（ + 2k +
k）。
{O left（n + { frac {n ^ {2}} {k}} + k right）}

。kが選択されている場合は注意してくださいk = Θ（（）。
{k = Theta（n）}

、次にバケットソートが実行されます O （（）。
{O（n）}

均一に分散された入力が与えられた場合の平均時間。

最適化
一般的な最適化は、バケットのソートされていない要素を最初に元の配列に戻し、次に配列全体に対して挿入ソートを実行することです。挿入ソートの実行時間は、各要素が最終位置からどれだけ離れているかに基づいているため、比較の数は比較的少なく、リストをメモリに連続して格納することで、メモリ階層をより有効に活用できます。
入力分布がわかっているか推定できる場合は、（単に一定のサイズを持つのではなく）一定の密度を含むバケットを選択できることがよくこれにより、 O （（）。
{O（n）}

入力が均一に分散されていなくても、平均時間計算量。

バリアント

一般的なバケットソート
バケットソートの最も一般的な変形は、ゼロから最大値Mまでのn個の数値入力のリストで動作し、値の範囲をそれぞれサイズM / nのn個のバケットに分割します。各バケットが挿入ソートを使用してソートされている場合、ソートは予想される線形時間で実行されるように表示できます（平均はすべての可能な入力に対して取得されます）。ただし、この種のパフォーマンスはクラスタリングによって低下します。多くの値が近くにある場合、それらはすべて1つのバケットに分類され、ゆっくりと並べ替えられます。このパフォーマンスの低下は、元のバケットソートアルゴリズムでは、入力が間隔[0，1）にわたって要素を均一に分散するランダムプロセスによって生成されると想定することで回避されます。

ProxmapSort
Proxmapの並べ替え
上記の一般的なバケットソートと同様に、ProxmapSortは、キーの半順序を保持する「マップキー」関数を使用して、キーの配列をサブ配列に分割することで機能します。各キーがそのサブ配列に追加されると、挿入ソートを使用してそのサブ配列がソートされたままになり、ProxmapSortが完了すると配列全体がソートされた順序になります。ProxmapSortは、マップキーを使用してデータをソートされた順序でほぼ同じ場所に配置し、キーの「proxmap」（近接マッピング）を生成するという点でバケットソートとは異なります。

ヒストグラムの並べ替え
ヒストグラムソートまたはカウントソートとして知られるバケットソートの別の変形は、カウント配列を使用して各バケットに分類される要素の数をカウントする初期パスを追加します。この情報を使用して、配列値を一連の交換によってインプレースの一連のバケットに配置でき、バケットストレージ用のスペースオーバーヘッドを残しません。

郵便配達員の種類
郵便配達のソートは、一般的な属性のセットによって説明された要素の階層構造、を利用してバケットソートの変種です。これは、郵便局のレターソーティングマシンで使用されるアルゴリズムです。メールは最初に国内と海外の間でソートされます。次に、州、州、または地域ごと。その後、目的地の郵便局で。キーは相互に比較されないため、ソート時間はO（cn）です。ここで、cはキーのサイズとバケットの数に依存します。これは、「トップダウン」または「最上位桁が最初」で機能する基数ソートに似ています。

シャッフルソート
シャッフルソートの最初の1/8除去することによって開始するバケットソートの変異体であるN個の、ソートするアイテムを再帰的にそれらをソートし、そしてアレイを入れ、それらを。これにより、残りの7/8のアイテムが配布されるn / 8の「バケット」が作成されます。次に、各「バケット」が並べ替えられ、「バケット」が連結されて並べ替えられた配列になります。

他のソートアルゴリズムとの比較
バケットソートは、カウントソートの一般化と見なすことができます。実際、各バケットのサイズが1の場合、バケットソートはカウントソートに縮退します。バケットソートの可変バケットサイズにより、O（M）メモリの代わりにO（n）メモリを使用できます。ここで、Mは個別の値の数です。代わりに、ソートのO（n + M）の最悪の場合の動作のカウントをあきらめます。
2つのバケットを使用したバケットソートは、実質的にクイックソートのバージョンであり、ピボット値は常に値の範囲の中間値として選択されます。この選択は均一に分散された入力に効果的ですが、ランダムに選択されたピボットなど、クイックソートでピボットを選択する他の手段により、入力分布でのクラスタリングに対する耐性が高まります。
N -wayマージソートアルゴリズムはまたにリストを配布することによって始まるNサブリストとそれぞれのソート。ただし、mergesortによって作成されたサブリストの値の範囲は重複しているため、バケットソートのように単純な連結で再結合することはできません。代わりに、マージアルゴリズムによってインターリーブする必要がただし、この追加費用は、より単純な分散フェーズと、各サブリストが同じサイズであることを保証する機能によって相殺され、最悪の場合の適切な期限が提供されます。
トップダウン基数ソートは、値の範囲とバケット数の両方が2の累乗に制限されているバケットソートの特殊なケースと見なすことができます。したがって、各バケットのサイズも2の累乗であり、この手順を再帰的に適用できます。このアプローチでは、各要素のビット表現のプレフィックスを調べてバケットを決定するだけでよいため、散布フェーズを加速できます。

参考文献
^ トーマス・H・コーメン。Charles E. Leiserson ; ロナルド・L・リベスト＆クリフォード・スタイン。アルゴリズムの概要。バケットソートは平均して線形時間で実行されます。ソートのカウントと同様に、バケットソートは入力について何かを想定しているため高速です。カウントソートは、入力が狭い範囲の整数で構成されていることを前提としていますが、バケットソートは、入力が間隔[0，1）にわたって要素を均一に分散するランダムプロセスによって生成されることを前提としています。バケットソートの考え方は、間隔[0、1）をn個の等しいサイズのサブ間隔、つまりバケットに分割し、n個の入力番号をバケットに分配することです。入力は[0、1）に均一に分散されているため、各バケットに多くの数値が含まれるとは思われません。出力を生成するには、各バケットの番号を並べ替えてから、バケットを順番に調べて、それぞれの要素を一覧表示します。
^ Corwin、E。およびLogar、A。「線形時間でのソート—バケットソートのバリエーション」。Journal of Computing Sciences in Colleges、20、1、pp.197–202。2004年10月。
^ Thomas H. Cormen、 Charles E. Leiserson、 Ronald L. Rivest、およびCliffordStein。アルゴリズム入門、第2版。MITプレスとマグロウヒル、2001年 ISBN 0-262-03293-7。セクション8.4：バケットソート、pp.174–177。
^ NISTのアルゴリズムとデータ構造の辞書：ヒストグラムの並べ替え
^ http://www.rrsd.com/psort/cuj/cuj.htm
^ ジョンコーエンからの革新的な新しい種類1997年11月26日
ポール・E.ブラック「郵便配達のソート」からのアルゴリズムとデータ構造の辞書ではNIST。
ロバート・ラミー’「郵便配達員の仕分け」 Cユーザージャーナル1992年8月
NISTのアルゴリズムとデータ構造の辞書：バケットソート

外部リンク
AnsiCのバケットソートコード
デモ付きバケットソートのバリエーション

「https://en.wikipedia.org/w/index.php?title=Bucket_sort&oldid=1049334903」
から取得”