Cでスロー基数ソート

Question

配列を昇順で並べ替える必要があり、時間の複雑さはO（n）でなければなりません。私は基数ソートを使用しており、それは十分に速くはありません。どのように私のコードをより速くすることができる任意のアイデアですか？ここでは、次のとおりです。

void radix(int *a, int n) { 

    int i; 
    int sorted[n]; 
    int number = 1; 
    int biggestNumber = -1; 

for(i = 0; i < n; i++){ 
    if(a[i] > biggestNumber) 
     biggestNumber = a[i]; } 


while (biggestNumber/number > 0){ 

int bucket[10] = { 0 }; 

    for (i = 0; i < n; i++) 
     bucket[(a[i]/number) % 10]++; 

    for (i = 1; i < 10; i++) 
     bucket[i] += bucket[i - 1]; 

    for (i = n - 1; i >= 0; i--) 
     sorted[--bucket[(a[i]/number) % 10]] = a[i]; 


    for (i = 0; i < n; i++) 
     a[i] = sorted[i]; 

     number*= 10; } } 

Answer 1

コメント - ソートのみ[i]が負の場合、負のインデックスがバケツのために使用され、正の数で動作するように表示される[...]と[ソート... ]。符号付き整数が必要ない場合は、これを変更して符号なし整数をソートすることができます。 number * = 10にオーバーフローのチェックはありません。ソートはスタックから割り当てられていますが、nが大きい場合は動作しません。 malloc（）を使用して、ソートされるスペースを割り当てます。

速くソートを行うには：

変更10から256までの基数のベース可能なオーバーフローを避けるために、ループから抜け出すために0 ==（数* = 256）を確認してください。

各パスで基数ソートの方向を変更します。 aからソートされた次のパス、ソートされたものからaへの次のパス。これは、各パスでスワップされるポインタのペアを使用すると最も簡単です。次に、ソートが完了した後、ソートされたデータが[]で終わっているかどうかを調べ、ソートされていない場合はsorted []から[]にコピーします。

バケットを行列にします。 intが32ビットで、基数が256であるとすると、バケットは[4] [256]になります。これにより、バケット行列を作成するための[]への単一パスが可能になります。 intが64ビットの場合、バケットは[8] [256]になります。