アルゴリズムクイックリファレンス 第2版

4.6

 バケツソート

■

87

例

4-8

 範囲

[0, 1)

のための関数

hash

と

numBuckets

static int num;

/*

使うバケツの個数は、要素数に同じ。

*/

int numBuckets(int numElements) {

num = numElements;

return numElements;

}

/**

*

要素にバケツの番号を割り振るハッシュ関数。バケツ内で要素が順に並ぶように、

*

要素の符号化を適宜調整する。数の範囲は

[0, 1)

なので、

*

バケツをサイズ

1/num

で再分割する。

*/

int hash(double *d) {

int bucket = num*(*d);

return bucket;

}

バケツには、固定サイズの配列を使っても構わないが、固定サイズの配列はバケ

ツが満杯になったら再割り当ての必要がある。リンク付きリストの実装の方が、

30

〜

40

％高速となる。

4.6.2

 分析

例4-7の関数

sortPointers

は、入力の各要素を、与えられた関数

hash

に基づき、

対応するバケツに格納する。これは

O(n)

時間かかる。

hash

の設計要件から、

i

＜

j

なら、バケツ

b

i

のすべての要素が、バケツ

b

j

のどの要素よりも小さいことがわかっ

ている。

バケツから値を取り出し入力配列に書き戻すとき、バケツに複数の要素があれば

挿入ソート

を使う。

バケツソート

が

O(n)

の振る舞いをするには、各バケツの整列

に必要な時間をすべて足し合わせても

O(n)

であることを保証しなければな ...