

バケツソート(Bucket
Sort)の平均計算量はO(n)ですが、もしデータが均一に分布してない場合、最悪計算量はO(n^2)になってしまいます。しかし、その場合他のアルゴリズムと組み合わせることによって計算量は改善できるのでしょうか？

教科書からの問題なのですが、二分探索を使用できるというヒントを与えられました。しかし、二分探索を使用する意味がよくわかりません。Merge
Sortを組み合わせたならO(nlogn)まで削減できますが、その他の方法が思いつきません。なにかアイデアを共有していただけると嬉しいです。

バケツソート  
ref: Algorithm Introduction, MIT Press

擬似コードへの入力は要素数 n の配列 A であり，各要素 A[i] は 0≤ A[i] < 1 を満たすと仮 定する．連結リストを要素とする補助配列
B0..n−1 を擬似コードは使用するが， リストを維持する機構は（擬似コードの外に）存在すると仮定する

[code]

    BUCKET-SORT(A) 
    1 n = A.length 
    2 B[0..n−1] を新しい配列とする 
    3 for i =0to n−1 
    4     B[i] を空リストに初期化する 
    5 for i =1to n 
    6     A[i] をリスト B[nA[i]] に挿入する 
    7 for i =0to n−1 
    8     リスト B[i] を挿入ソートでソートする 
    9 リスト B[0],B[1],...,B[n−1] をこの順序で連接する
    
[/code]


CC BY-SA 4.0
2020-05-05T07:40:37.110
66317
2020-05-05T12:36:24.550
2020-05-05T12:36:24.550
38330
38330
question
c アルゴリズム データ構造
バケツソートの最低ケースを改善するためには