基数ソートはC++で実装されています

Question

1から10^6までの大量のプログラムを作成してC++を改善しようとしています。各パスに数値を格納するバケットは、ノードの配列です（nodeは値と次のノード属性を含む構造体です）。

数値を最小値に応じてバケットにソートした後、別のバケットの先頭に1つのバケットポイントの終わりがあります（注文を中断することなく保存された番号をすばやく得ることができます）。私のコードにはエラーはありません（コンパイルまたはランタイムのいずれか）が、残りの6回の繰り返しを解決する方法について壁に当たっています。

私が抱えている問題は、最初は数値がint配列の形でradixSort関数に供給されたことです。並べ替えの最初の反復の後、数値は構造体の配列に格納されます。私は私のコードを再作成して7回の反復のために1つのforループを持つようにする方法はありますか？または1回実行されるループに対して1つ必要ですか？6回実行して完全にソートされたリスト？

#include <iostream> 
#include <math.h> 
using namespace std; 

struct node 
{ 
    int value; 
    node *next; 
}; 

//The 10 buckets to store the intermediary results of every sort 
node *bucket[10]; 
//This serves as the array of pointers to the front of every linked list 
node *ptr[10]; 
//This serves as the array of pointer to the end of every linked list 
node *end[10]; 
node *linkedpointer; 
node *item; 
node *temp; 

void append(int value, int n) 
{ 
    node *temp; 
    item=new node; 
    item->value=value; 
    item->next=NULL; 
    end[n]=item; 
    if(bucket[n]->next==NULL) 
    { 
     cout << "Bucket " << n << " is empty" <<endl; 
     bucket[n]->next=item; 
     ptr[n]=item; 
    } 
    else 
    { 
     cout << "Bucket " << n << " is not empty" <<endl; 
     temp=bucket[n]; 
     while(temp->next!=NULL){ 
      temp=temp->next; 
     } 
     temp->next=item; 
    } 
} 

bool isBucketEmpty(int n){ 
    if(bucket[n]->next!=NULL) 
     return false; 
    else 
     return true; 
} 
//print the contents of all buckets in order 
void printBucket(){ 
    temp=bucket[0]->next; 
    int i=0; 
    while(i<10){ 
     if(temp==NULL){ 
      i++; 
      temp=bucket[i]->next;      
     } 
     else break; 

    } 
    linkedpointer=temp; 
    while(temp!=NULL){ 
     cout << temp->value <<endl; 
     temp=temp->next; 
    } 
} 

void radixSort(int *list, int length){ 
    int i,j,k,l; 
    int x; 
    for(i=0;i<10;i++){ 
     bucket[i]=new node; 
     ptr[i]=new node; 
     ptr[i]->next=NULL; 
     end[i]=new node; 
    } 
    linkedpointer=new node; 

    //Perform radix sort 
    for(i=0;i<1;i++){ 
     for(j=0;j<length;j++){   
      x=(int)(*(list+j)/pow(10,i))%10;    
      append(*(list+j),x); 
      printBucket(x); 
     }//End of insertion loop 
     k=0,l=1; 

     //Linking loop: Link end of one linked list to the front of another 
     for(j=0;j<9;j++){ 
      if(isBucketEmpty(k)) 
       k++; 
      if(isBucketEmpty(l) && l!=9) 
       l++; 
      if(!isBucketEmpty(k) && !isBucketEmpty(l)){ 
       end[k]->next=ptr[l]; 
       k++; 
       if(l!=9) l++; 
      } 

     }//End of linking for loop 

     cout << "Print results" <<endl; 
     printBucket(); 

     for(j=0;j<10;j++) 
      bucket[i]->next=NULL;      
     cout << "End of iteration" <<endl; 
    }//End of radix sort loop 
} 

int main(){ 
    int testcases,i,input; 
    cin >> testcases; 
    int list[testcases]; 
    int *ptr=&list[0]; 
    for(i=0;i<testcases;i++){ 
     cin>>list[i]; 
    } 

    radixSort(ptr,testcases); 
    return 0; 
} 

Answer 1

私はあなたのソリューションが過度に複雑になっていると思います。入力で受け取った単一の配列を使用して基数を実装できます。各ステップのバケットは、入力配列の各バケットの開始インデックスを示すインデックスの配列で表されます。実際に

、あなたも再帰的にそれを行うことができます：もちろんbuckets[i+1] - buckets[i]の

// Sort 'size' number of integers starting at 'input' according to the 'digit'th digit 
// For the parameter 'digit', 0 denotes the least significant digit and increases as significance does 
void radixSort(int* input, int size, int digit) 
{ 
    if (size == 0) 
     return; 

    int[10] buckets; // assuming decimal numbers 

    // Sort the array in place while keeping track of bucket starting indices. 
    // If bucket[i] is meant to be empty (no numbers with i at the specified digit), 
    // then let bucket[i+1] = bucket[i] 

    for (int i = 0; i < 10; ++i) 
    { 
     radixSort(input + buckets[i], buckets[i+1] - buckets[i], digit+1); 
    } 
} 

をiが9であるとき、バッファオーバーフローを引き起こすが、私は、余分なチェックや読みやすさのために省略されます。私はあなたがそれをどう扱うかを知っていると信じている

radixSort(testcases, sizeof(testcases)/sizeof(testcases[0]), 0)を呼び出すだけで、配列をソートする必要があります。

Answer 2

あなたの値は0の範囲内のint型なので... 1,000,000

あなたはサイズ1000001ののint配列を作成し、に二番目の配列INIT 2回のパスで

を全体のことを行うことができますすべてゼロ。

入力配列をパススルーし、その値を添え字 として使用して、2番目の配列の値をインクリメントします。

これを実行すると、2回目のパスが簡単になります。 は2番目の配列を通り、各要素は元の配列に という数字が何回現れたかを示します。この情報を使用して、入力配列 を再入力します。

Answer 3

より良いメモリ管理で処理を高速化するには、配列を1回通過させることでインデックスに変換されるカウント用の行列を作成します。配列がソートされるまで、元の配列と同じサイズの2番目の一時配列と2つの配列間の基数ソートを割り当てます。奇数回の基数ソート・パスが実行された場合、temp配列は最後に元の配列にコピーする必要があります。

さらに処理を高速化するには、基数ソートに基数10の代わりに基数256を使用します。これは、行列を作成するために1回のスキャンパスと、ソートを行うために4つの基数ソートパスを必要とします。コード例：

typedef unsigned int uint32_t; 

uint32_t * RadixSort(uint32_t * a, size_t count) 
{ 
size_t mIndex[4][256] = {0};   // count/index matrix 
uint32_t * b = new uint32_t [COUNT]; // allocate temp array 
size_t i,j,m,n; 
uint32_t u; 
    for(i = 0; i < count; i++){   // generate histograms 
     u = a[i]; 
     for(j = 0; j < 4; j++){ 
      mIndex[j][(size_t)(u & 0xff)]++; 
      u >>= 8; 
     }  
    } 
    for(j = 0; j < 4; j++){    // convert to indices 
     m = 0; 
     for(i = 0; i < 256; i++){ 
      n = mIndex[j][i]; 
      mIndex[j][i] = m; 
      m += n; 
     }  
    } 
    for(j = 0; j < 4; j++){    // radix sort 
     for(i = 0; i < count; i++){  // sort by current lsb 
      u = a[i]; 
      m = (size_t)(u>>(j<<3))&0xff; 
      b[mIndex[j][m]++] = u; 
     } 
     std::swap(a, b);    // swap ptrs 
    } 
    delete[] b; 
    return(a); 
}