Ich versuche mein C ++ zu verbessern, indem ich ein Programm erstelle, das eine große Anzahl von Zahlen zwischen 1 und 10 ^ 6 akzeptiert. Die Buckets, in denen die Zahlen in jedem Durchgang gespeichert werden, sind ein Array von Knoten (wobei Knoten eine von mir erstellte Struktur ist, die einen Wert und ein Attribut für den nächsten Knoten enthält).

Nachdem ich die Zahlen nach dem niedrigstwertigen Wert in Eimern sortiert habe, habe ich das Ende eines Eimers an den Anfang eines anderen Eimers (damit ich die Zahlen schnell speichern kann, ohne die Reihenfolge zu stören). Mein Code enthält keine Fehler (weder beim Kompilieren noch zur Laufzeit), aber ich habe eine Frage, wie ich die verbleibenden 6 Iterationen lösen werde (da ich den Zahlenbereich kenne).

Das Problem, das ich habe, ist, dass anfangs die Zahlen in Form eines Int-Arrays an die RadixSort-Funktion übergeben wurden. Nach der ersten Iteration der Sortierung werden die Zahlen nun im Array von Strukturen gespeichert. Gibt es eine Möglichkeit, meinen Code zu überarbeiten, sodass ich nur eine for-Schleife für die 7 Iterationen habe, oder brauche ich eine for-Schleife, die einmal ausgeführt wird, und eine weitere Schleife darunter, die sechsmal ausgeführt wird, bevor die vollständig sortierte zurückgegeben wird? 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;
}