バケットソートの分割統治
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 09:14 UTC 版)
「バケットソート」の記事における「バケットソートの分割統治」の解説
仮に32ビット整数をソートする場合に、約43億個のバケツを持つことは非現実的である。バケツは1つの値に対して1つのバケツを用意する必要はなく、範囲を持ったバケツが矛盾なくソートされていれば良い。この時、各バケツの中身は別ソートアルゴリズムでソートしてやるか、再度バケットソートを適用する必要がある。 冒頭の32ビット整数を1ビットずつ再帰的にバケットソートすると、32階層のバケットソートが必要になる。これは約43億個に対してのlogであり、バケットソートもまたlogのオーダーから抜け出せていないことが分かる。（2ビットずつ処理しても4ビットずつ処理しても、やはりlogは消えない。） 通常、各値の取りうる範囲よりも、ソートすべき配列サイズの方が小さいため、バケットソートはO(nlogn)ソートよりも実質低速であることが多い。 また、文字列に対しても、頭から1文字ずつ再帰的にバケットソートを行うことができる。32ビット整数のソートは、長さ32の1ビット文字からなる文字列をソートしているとみなすこともできる。
※この「バケットソートの分割統治」の解説は、「バケットソート」の解説の一部です。
「バケットソートの分割統治」を含む「バケットソート」の記事については、「バケットソート」の概要を参照ください。
ウィキペディア小見出し辞書の「バケットソートの分割統治」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- バケットソートの分割統治のページへのリンク
