バケットソート

入力に互いに近いキーが複数含まれている場合（クラスタリング）、それらの要素は同じバケットに配置される可能性が高く、その結果、一部のバケットには平均よりも多くの要素が含まれることになります。最悪のシナリオは、すべての要素が単一のバケットに配置される場合です。この場合、全体のパフォーマンスは、各バケットをソートするために使用されるアルゴリズムによって大きく左右されます。たとえば、${\displaystyle O(n^{2})}$挿入ソートまたは${\displaystyle O(n\log(n))}$マージソートなどの比較ソートアルゴリズム。

入力が均一に分布している場合を考えてみましょう。最初のステップであるバケットの初期化と配列内の最大キー値の検索は、次のように実行できます。${\displaystyle O(n)}$時間。除算と乗算が一定時間で実行できる場合、各要素をそれぞれのバケットに分散させるのにもコストがかかります。${\displaystyle O(n)}$各バケットのソートに挿入ソートを使用すると仮定すると、3 番目のステップのコストは${\displaystyle O(\textstyle \sum _{i=1}^{k}\displaystyle n_{i}^{2})}$、 どこ${\displaystyle n_{i}}$バケットの長さはインデックス付けされています${\displaystyle i}$平均時間について考えているので、期待値は${\displaystyle E(n_{i}^{2})}$代わりに評価する必要があります。${\displaystyle X_{ij}}$確率変数とは、${\displaystyle 1}$要素の場合${\displaystyle j}$バケツに入れられる${\displaystyle i}$、 そして${\displaystyle 0}$そうでなければ。${\displaystyle n_{i}=\sum _{j=1}^{n}X_{ij}}$。 したがって、

${\displaystyle {\begin{aligned}E(n_{i}^{2})&=E\left(\sum _{j=1}^{n}X_{ij}\sum _{l=1}^{n}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}\sum _{l=1}^{n}X_{ij}X_{il}\right)\\&=E\left(\sum _{j=1}^{n}X_{ij}^{2}\right)+E\left(\sum _{1\leq j,l\leq n}\sum _{j\neq l}X_{ij}X_{il}\right).\end{aligned}}}$

最後の行は総和をケースごとに分割します${\displaystyle j=l}$そしてケース${\displaystyle j\neq l}$オブジェクトがバケットに分散される可能性${\displaystyle i}$は${\displaystyle 1/k}$、${\displaystyle X_{ij}}$確率1で${\displaystyle 1/k}$それ以外の場合は0。

${\displaystyle E(X_{ij}^{2})=1^{2}\cdot \left({\frac {1}{k}}\right)+0^{2}\cdot \left(1-{\frac {1}{k}}\right)={\frac {1}{k}}}$

${\displaystyle E(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}}$

合計すると、

${\displaystyle 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)=n\cdot {\frac {1}{k}}+n(n-1)\cdot {\frac {1}{k^{2}}}={\frac {n^{2}+nk-n}{k^{2}}}}$

最後に、複雑さは${\displaystyle 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)}$。

バケットソートの最後のステップは、各バケット内のソート済みオブジェクトをすべて連結することです。${\displaystyle O(k)}$時間。したがって、全体の複雑さは${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$k を次のように選択すると、${\displaystyle k=\Theta (n)}$バケットソートは${\displaystyle O(n)}$一様分布の入力が与えられた場合の平均時間。^{[ 1 ]}

バケットソートの最も一般的なバリアントは、0 からある最大値Mまでのn 個の数値入力のリストに対して動作し、値の範囲をそれぞれサイズM / bのb 個のバケットに分割します。各バケットを挿入ソートを使用してソートすると、ソートは期待線形時間で実行されることが示されています (すべての可能な入力について平均が取られます)。^{[ 3 ]}ただし、このソートのパフォーマンスはクラスタリングによって低下します。多くの値が近くに発生すると、それらはすべて単一のバケットに落ち込み、ソートが遅くなります。このパフォーマンスの低下は、入力が区間[0,1)に要素を均等に分布させるランダムプロセスによって生成されると仮定することで、元のバケットソートアルゴリズムで回避されています。^{[ 1 ]}

前述の一般的なバケットソートと同様に、ProxmapSort は、キーの部分的な順序を保持する「マップキー」関数を使用してキーの配列をサブ配列に分割することで機能します。各キーがサブ配列に追加される際に、挿入ソートを使用してそのサブ配列のソート状態を維持し、ProxmapSort が完了すると配列全体がソートされた状態になります。ProxmapSort は、マップキーを使用してデータをソートされた順序で適切な場所に配置する点でバケットソートと異なり、キーの「プロックスマップ」（近接マッピング）を生成します。

バケットソートの別のバリアントであるヒストグラムソートまたはカウンティングソートでは、カウント配列を使用して各バケットに収まる要素の数をカウントする最初のパスが追加されます。^{[ 4 ]}この情報を使用して、配列の値は交換のシーケンスによってその場でバケットのシーケンスに配置され、バケットのストレージのためのスペースのオーバーヘッドは発生しません。

ポストマンソートは、要素の階層構造を利用するバケットソートの一種で、通常は属性のセットで記述されます。これは、郵便局の郵便仕分け機で使用されているアルゴリズムです。郵便物はまず国内郵便と国際郵便に分けられ、次に州、県、または準州ごとに、次に宛先の郵便局ごとに、次にルートごとに、といった具合に仕分けされます。キー同士が比較されないため、ソート時間は O( cn ) で、c はキーのサイズとバケットの数に依存します。これは、「トップダウン」または「最上位桁から」動作する基数ソートに似ています。 ^{[ 5 ] [ 6 ]}

シャッフルソート^{[ 7 ]}はバケットソートの変種で、まずソート対象のn個のアイテムのうち最初の1/8を取り除き、それらを再帰的にソートして配列に格納します。これにより、残りの7/8個のアイテムが分配されるn /8個の「バケット」が作成されます。次に、各「バケット」がソートされ、それらの「バケット」が連結されてソート済みの配列が作成されます。