バケットソート

バケットソート

クラス	ソートアルゴリズム
データ構造	配列
最悪の場合の パフォーマンス	${\displaystyle O\left(n^{2}\right)}$
平均的 なパフォーマンス	${\displaystyle O\left(n+{\frac {n^{2}}{k}}+k\right)}$ここで、k はバケットの数です。${\displaystyle O(n),{\text{k\approx n の場合}$
最悪の場合の 空間複雑度	${\displaystyle O(n+k)}$

バケット ソート、またはビン ソートは、配列の要素を複数のバケットに分散するソート アルゴリズムです。各バケットは、異なるソート アルゴリズムを使用するか、バケット ソート アルゴリズムを再帰的に適用して個別にソートされます。これは、バケットごとに複数のキーを許可するピジョンホール ソートの一般化である分散ソートであり、最上位桁から最下位桁への形式の基数ソートの親戚です。バケット ソートは比較を使用して実装できるため、比較ソートアルゴリズムと見なすこともできます。計算の複雑さは、各バケットのソートに使用するアルゴリズム、使用するバケットの数、および入力が均一に分散されているかどうかによって異なります。

バケットソートは次のように機能します。

1. 最初は空の「バケット」の配列を設定します。
2. 散布: 元の配列を調べて、各オブジェクトをバケットに配置します。
3. 空でない各バケットをソートします。
4. Gather : バケットを順番に訪問し、すべての要素を元の配列に戻します。

関数bucketSort(array, k)は
    バケット ← k 個の空リストの新しい配列
    M ← 1 + 配列内の最大キー値
    i = 0からlength(array)まで配列[i]をバケット[floor ( k × array[i] / M)]に
        挿入します。i = 0からkまで
     
        次のソート(バケット[i])
    バケット[0]、...、バケット[k]の連結
を返す

array はソートする配列、k は使用するバケットの数を表します。すべてのキーを 1 回反復処理することで、最大のキー値を線形時間で計算できます。浮動小数点数を整数に変換するにはfloor 関数を使用する必要があります (データ型のキャストも必要になる場合があります)。関数nextSortは、各バケットをソートするために使用されるソート関数です。従来、挿入ソートが使用されますが、選択ソートやマージ ソートなどの他のアルゴリズムも使用できます。bucketSort自体を nextSortとして使用すると、基数ソートの関連が生成されます。特に、n = 2の場合はクイックソートに相当します(ただし、ピボットの選択が適切でない可能性があります)。

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

入力が均一に分散している場合を考えてみましょう。最初のステップであるバケットの初期化と配列の最大キー値の検出は、 で実行できます。除算と乗算が定数時間で実行できる場合、各要素をバケットに分散させるのにも のコストがかかります。挿入ソートを使用して各バケットをソートすると、3 番目のステップのコストは で、 はインデックス のバケットの長さです。平均時間について考えているため、代わりに期待値を評価する必要がります。要素がバケット に配置されている場合は、それ以外の場合は となるランダム変数を とします。 となります。したがって、 ${\displaystyle O(n)}$${\displaystyle O(n)}$${\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}}}$

最後の行は、合計を の場合と の場合に分けます。オブジェクトがバケットに分配される確率は であるため、確率が の場合は 1 、それ以外の場合は 0 になります。 ${\displaystyle j=l}$${\displaystyle j\neq l}$${\displaystyle i}$${\displaystyle 1/k}$${\displaystyle X_{ij}}$${\displaystyle 1/k}$

${\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)}$

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

一般的な最適化は、まずバケットのソートされていない要素を元の配列に戻し、次に配列全体に対して挿入ソートを実行することです。挿入ソートの実行時間は各要素が最終位置からどれだけ離れているかに基づいているため、比較の回数は比較的少なく、リストをメモリ内に連続して保存することでメモリ階層をより有効に活用できます。^[2]

入力分布が既知であるか、または推定できる場合、一定の密度 (単に一定のサイズを持つのではなく) を含むバケットを選択できることがよくあります。これにより、入力が均一に分布していなくても、平均時間計算量が可能になります。 ${\displaystyle O(n)}$

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

上で説明した一般的なバケット ソートと同様に、ProxmapSort は、キーの部分的な順序を保持する「マップ キー」関数を使用して、キーの配列をサブ配列に分割することによって機能します。各キーがサブ配列に追加されると、挿入ソートを使用してサブ配列がソートされた状態が維持され、ProxmapSort が完了すると配列全体がソートされた順序になります。ProxmapSort は、マップ キーを使用してデータをソートされた順序で大まかに配置する点でバケット ソートと異なり、キーの「proxmap」(近接マッピング) を生成します。

ヒストグラムソートまたはカウンティングソートと呼ばれるバケットソートの別のバリエーションでは、カウント配列を使用して各バケットに入る要素の数をカウントする最初のパスが追加されます。^[4]この情報を使用すると、配列の値は一連の交換によってインプレースのバケットのシーケンスに配置でき、バケットのストレージにオーバーヘッドスペースが残りません。^{[検証失敗]}

ポストマンソートは、バケットソートの一種で、通常は属性のセットで記述される要素の階層構造を活用します。これは、郵便局の郵便物仕分け機で使用されているアルゴリズムです。郵便物は、まず国内と海外で仕分けされ、次に州、県、または地域、宛先の郵便局、ルートなどによって仕分けされます。キーは互いに比較されないため、ソート時間は O( cn ) です。ここで、c はキーのサイズとバケットの数によって異なります。これは、 「トップダウン」または「最上位桁を先頭に」動作する基数ソートに似ています。^[5]

シャッフルソート^[6]はバケットソートの変形で、ソートするn個の項目の最初の1/8を削除し、それらを再帰的にソートして配列に格納します。これにより、n /8個の「バケット」が作成され、残りの7/8個の項目が分配されます。次に、各「バケット」がソートされ、「バケット」が連結されてソートされた配列になります。

バケット ソートは、カウンティング ソートの一般化と見ることができます。実際、各バケットのサイズが 1 の場合、バケット ソートはカウンティング ソートに退化します。バケット ソートの可変バケット サイズにより、O( M ) メモリの代わりに O( n ) メモリを使用できます ( Mは異なる値の数)。その代わりに、カウンティング ソートの O( n + M ) 最悪のケースの動作は 放棄されます。

2 つのバケットを使用したバケット ソートは、実質的にはクイックソートの一種であり、ピボット値は常に値の範囲の中央値に選択されます。この選択は均一に分散された入力には効果的ですが、ランダムに選択されたピボットなど、クイックソートでピボットを選択する他の手段を使用すると、入力分布のクラスタリングに対する耐性が高まります。

n方向のマージソートアルゴリズムも、リストをn 個のサブリストに分散し、各サブリストをソートすることから始まります。ただし、マージソートによって作成されたサブリストには重複する値の範囲があるため、バケット ソートのように単純な連結で再結合することはできません。代わりに、マージ アルゴリズムによってサブリストをインターリーブする必要があります。ただし、この追加コストは、より単純なスキャッター フェーズと、各サブリストが同じサイズであることを保証し、最悪ケースの時間制限を適切に設定する機能によって相殺されます。

トップダウン基数ソートは、値の範囲とバケットの数の両方が 2 の累乗に制限されるバケット ソートの特殊なケースと見なすことができます。したがって、各バケットのサイズも 2 の累乗になり、手順を再帰的に適用できます。このアプローチでは、各要素のビット表現のプレフィックスを調べてバケットを決定するだけでよいため、スキャッター フェーズを高速化できます。

• Paul E. Black「Postman's Sort」、NISTのアルゴリズムとデータ構造の辞書より。
• ロバート・レイミー「郵便配達人の分類」C ユーザーズ ジャーナル1992 年 8 月
• NIST のアルゴリズムとデータ構造の辞書: バケット ソート

• Ansi C のバケット ソート コード
• デモ付きバケットソートのバリエーション