Radix並べ替えを実施C++

Question

私向上させる"という私のC++によるプログラムを作ることで大量の数を1、10^6.のバケットデータを蓄積するとともに、数値は各パスの配列であるノード（ノードは、structでの作を含む価値の次のノードの属性）に指定します。

後の選別のための多くのバケットによると、少なくとも重要な価値を持っていを終えたバケットの先頭のバケット(ができるように番号を格納されるようになっていを中断させることなくするクラスです。私のコードに誤りがないかをコンパイルや実行時には打っ壁について私を解決する残りの6回(かいの範囲の数).

の問題がんは、最初の番号が供給されるradixSort機能をint配列の型になります。後に繰り返し処理の最初の仕分け、その数は現在格納される配列の構造体.はありませんが直自分のコードでいくつのループに7回、私は必要なためループを実行するには、一度別のループ以下でないことにご注意願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

私は、あなたが深刻なソリューションを過度に複雑だと思います。単一のアレイは、入力アレイ内の各バケットの開始インデックスをマークするインデックスの配列で表される各ステップにおけるバケットと、入力で受信使用基数を実装することができます。

実際には、あなたも再帰的にそれを行うことができます：

// 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);
    }
}

buckets[i+1] - buckets[i]が9であるとき、

コースiのは、バッファオーバーフローが発生しますが、私は、余分なチェックや読みやすさのために省略しました。私はあなたがそれを処理する方法を知っている信頼しています。

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

Answer 2

よりよいメモリ管理とプロセスをスピードアップするために、アレイ上に単一パスを作ることによってインデックスに変換取得カウントのためのマトリックスを作成します。アレイがソートされるまで、二つの配列の間の元の配列、および基数ソートのような第2の一時配列同じサイズを割り当てます。基数ソートの奇数が行われ合格した場合、その後、一時アレイは端部で元の配列にコピーバックする必要があります。

さらなるプロセスをスピードアップするために、基数ソートのためにベース256の代わりに、ベース10を使用します。これは、マトリックスと4基数ソートを作成するために、1つのスキャンパスを取るの並べ替えを行うに渡します。コード例：

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);
}

Answer 3

からの値がintの範囲を0...1,000,000

を作成できますが、intの配列のサイズ1,000,001は、この二つのパス

Initの配列をすべてゼロのままにしてお

を通過ご入力配列の値として、下付き文字 に増加価値の配列になります。

だがその後のパスが容易です。徒歩の配列の各要素をうまくる 多数登場の配列になります。利用情報をrepopulate 入力配列の型になります。