バケットソート

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

ソートアルゴリズム

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

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

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

擬似コード

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

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

分析

最悪のケース分析

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

平均ケース分析

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

{\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 になります。 $j=l$ $j\neq l$ $i$ $1/k$ $X_{ij}$ $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(X_{ij}X_{ik})=1\cdot \left({\frac {1}{k}}\right)\left({\frac {1}{k}}\right)={\frac {1}{k^{2}}}

合計すると、

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}}}

最終的に、複雑さは次のようになります。 $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] $O(k)$ $O\left(n+{\frac {n^{2}}{k}}+k\right)$ $k=\Theta (n)$ $O(n)$

最適化

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

入力分布が既知であるか推定可能な場合、（単に一定の大きさを持つのではなく）一定密度のバケットを選択できる場合が多い。これにより、入力が均一に分布していなくても、平均計算時間を実現できる。 $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のべき乗となり、手順を再帰的に適用できます。このアプローチは、各要素のビット表現のプレフィックスを調べるだけでバケットを決定できるため、スキャッタリングフェーズを高速化します。

参考文献

^ ab Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest & Clifford Stein .アルゴリズム入門.バケットソートは平均して線形時間で実行されます。カウンティングソートと同様に、バケットソートは入力について何かを仮定するため高速です。カウンティングソートでは入力が狭い範囲の整数で構成されていると仮定しますが、バケットソートでは入力が要素を区間[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、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年、ISBN 0-262-03293-7セクション8.4: バケットソート、pp.174–177。
^ NISTのアルゴリズムとデータ構造の辞書：ヒストグラムソート
^ 「Robert Ramey ソフトウェア開発」。
^ ジョン・コーエンによる革新的な新しいソート 1997年11月26日

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

外部リンク

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

[lfcs-1] Thomas H. Cormen ; Charles E. Leiserson ; Ronald L. Rivest & Clifford Stein .アルゴリズム入門.バケットソートは平均して線形時間で実行されます。カウンティングソートと同様に、バケットソートは入力について何かを仮定するため高速です。カウンティングソートでは入力が狭い範囲の整数で構成されていると仮定しますが、バケットソートでは入力が要素を区間[0,1)に均一に分布するランダムプロセスによって生成されると仮定します。バケットソートの考え方は、区間[0, 1)をn 個の等しいサイズのサブ区間、つまりバケットに分割し、 n 個の入力数値をバケットに分配することです。入力は[0, 1)に均一に分布しているので、各バケットに多くの数値が入るとは予想されません。出力を生成するには、各バケットの数値をソートし、バケットを順番に処理して各要素をリストします。

[2] Corwin, E. および Logar, A. 「線形時間でのソート — バケットソートのバリエーション」Journal of Computing Sciences in Colleges、20, 1、pp.197–202、2004年10月。

[3] Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein著『アルゴリズム入門第2版』MIT Press and McGraw-Hill、2001年、ISBN 0-262-03293-7セクション8.4: バケットソート、pp.174–177。

[4] NISTのアルゴリズムとデータ構造の辞書：ヒストグラムソート

[5] 「Robert Ramey ソフトウェア開発」。

[6] ジョン・コーエンによる革新的な新しいソート 1997年11月26日