Radix Sort in C ++ implementiert

Question

Ich versuche, meinen C ++ zu verbessern, indem ein Programm zu erstellen, die eine große Menge an Zahlen zwischen 1 und 10 ^ 6 statt. Die Schaufeln, die die Zahlen in jedem Durchlauf speichern werden ein Array von Knoten (in dem Knoten ist ein struct I einen Wert enthält, erstellt und ein nächstes Knotenattribut).

Nachdem die Zahlen in Eimern Sortieren entsprechend dem niedrigstwertigen Wert, ich habe das Ende einer Schaufel Punkt auf den Anfang eines anderen bucket (so dass ich schnell die Zahlen ohne Unterbrechung der Reihenfolge gespeichert werden, erhalten kann). Mein Code hat keine Fehler (entweder kompiliert oder Laufzeit), aber ich habe eine Wand schlagen darüber, wie ich die restlichen 6 Iterationen lösen werde (da ich den Bereich der Zahlen kennen).

Das Problem, das ich habe, ist, dass zunächst die Zahlen der RadixSort Funktion in Form eines int-Array geliefert wurden. Nach der ersten Iteration der Sortierung werden die Zahlen nun in dem Array von Strukturen gespeichert. Gibt es eine Möglichkeit, dass ich meinen Code überarbeiten könnte, so dass ich für die 7 Iterationen nur eine for-Schleife haben, oder muss ich eine for-Schleife, die einmal ausgeführt wird, und eine weitere Schleife darunter die 6-mal ausgeführt werden, bevor die vollständig sortiert Rückkehr Liste?

#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

Ich glaube, du bist stark Ihre Lösung overcomplicating. Sie können radix mit dem einzigen Array implementieren im Eingang empfing, mit den Eimern in jedem Schritt durch eine Reihe von Indizes dargestellt, die den Startindex jeder Schaufel in dem Eingangsfeld markieren.

In der Tat, man könnte es auch rekursiv tun:

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

Natürlich buckets[i+1] - buckets[i] einen Pufferüberlauf verursachen, wenn i 9 ist, aber ich weggelassen, um die zusätzliche Überprüfung oder Lesbarkeit willen; Ich hoffe, Sie wissen, wie das zu handhaben.

Damit Sie gerade anrufen haben radixSort(testcases, sizeof(testcases) / sizeof(testcases[0]), 0) und Array soll sortiert werden.

Answer 2

Um den Prozess mit einem besseren Speicherverwaltung, erstellen Sie eine Matrix für die Zählungen zu beschleunigen, die, indem sie einen einzigen Durchlauf über die Anordnung in Indizes konvertiert werden. Weisen Sie einen zweiten temporären Array die gleiche Größe wie das Original-Array und Radixsort zwischen den beiden Feldern, bis das Array sortiert ist. Wenn eine ungerade Anzahl von Radixsort Pässe durchgeführt wird, dann wird das temporäre Array müssen am Ende wieder auf den ursprünglichen Array kopiert werden.

Um den Prozess zu beschleunigen, verwendet Basis 256 anstelle von Basis 10 für den Radixsort. Dieser Vorgang dauert nur 1 Abtastdurchgang die Matrix und 4 Radixsort zu schaffen übergibt die Sortier zu tun. Beispielcode:

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

Da Ihre Werte sind Ints im Bereich von 0 ... 1.000.000

Sie können eine int-Array erstellen von der Größe 1000001, und tun das Ganze in zwei Durchgängen

Init das zweite Array auf Null.

Machen Sie einen Durchlauf durch Ihre Eingabe-Array, und verwenden Sie den Wert als Index den Wert in dem zweiten Feld zu inkrementieren.

Wenn Sie das tun, dann der zweite Durchlauf einfach ist. Spaziergang durch das zweite Array und jedes Element gibt an, wie viele Male, dass Zahl erschien in der ursprünglichen Anordnung. Nutzen Sie diese Informationen wieder zu bevölkern Ihre Eingabe-Array.