基数C++を使用してソート

Question

数字の束があるとします。まず、最下位桁を対応するバケットに入れなければなりません。例：530、まずバケツ0に入れなければなりません。番号61ではバケツ1に入れなければなりません。

多次元配列を使用してこれを行うことを計画しました。

int nrows = 10; 
    int ncolumns = 999999; 

    int **array_for_bucket = (int **)malloc(nrows * sizeof(int *)); 
     for(i = 0; i < nrows; i++) 
      array_for_bucket[i] = (int *)malloc(ncolumns * sizeof(int)); 

    left = (a->value)%10; 
    array_for_bucket[left][?? ] = a->value; 

その後、私は1つのノードを作成しました。だから私は（私はリストがどのように大規模になりますかわからないので）999999であるNROWS 2-dimenional配列は、10（0〜9の場合）とncolumnsで作成します電話する。このノードaには値50があります。入れたいバケットを見つけるには "left"を計算し、0を返します。だから私はバケット0にこのa->値を入れたいと思います。しかし今、私は立ち往生している。この値をバケットに入れるにはどうすればよいですか？私はこれを行うためにポインタ配列を使用する必要があります。

私は長い間考えていましたが、まだそれを行うには良い方法を見つけることができませんでした。だから私といくつかのアイデアを共有してください。ありがとうございました！

Answer 1

これはもっと簡単な方法ですが、radix*nkeysの代わりにnkeysサイズのバッファが必要です。

nkeysキーに適合する2番目のバッファを割り当てます。今すぐデータを最初に確認し、各バケットでいくつのキーが終了するかを単純に数えます。 radixサイズのポインタ配列を作成できます。各ポインタは出力バッファ内のそのバケットの先頭にあります。最後に、データはキーを移動しますが、2番目のパスになります。キーを移動するたびに、そのバケットポインタを増分します。

void radix_sort(int *keys, int nkeys) 
{ 
    int *shadow = malloc(nkeys * sizeof(*keys)); 

    int bucket_count[10]; 
    int *bucket_ptrs[10]; 
    int i; 

    for (i = 0; i < 10; i++) 
     bucket_count[i] = 0; 

    for (i = 0; i < nkeys; i++) 
     bucket_count[keys[i] % 10]++; 

    bucket_ptrs[0] = shadow; 
    for (i = 1; i < 10; i++) 
     bucket_ptrs[i] = bucket_ptrs[i-1] + bucket_count[i-1]; 

    for (i = 0; i < nkeys; i++) 
     *(bucket_ptrs[keys[i] % 10]++) = keys[i]; 

    //shadow now has the sorted keys 

    free(shadow); 
} 

しかし、私は質問を誤解している可能性があります

は、ここでのC++にするためにいくつかのCコードです。基数ソートとは少し違うことをしているなら、いくつかの詳細を追加してください。

Answer 2

ポインタを格納する場合は、ブーストPointer containersライブラリを参照してください。

Answer 3

C++は私の特典ではありませんが、wikipedia-Raidx Sortのこのコードは非常に包括的で、これまでに実装したものよりも多分C++です。それが欲しいと思っています。

Answer 4

これはC++で、もうmallocは使用しません。私たちはコンテナを使用します。 2次元配列はベクトルのベクトルです。

vector<vector<int> > bucket(10); 
left = (a->value)%10; 
bucket[left].push_back(a->value);