Ich versuche, mein C++ zu verbessern, indem ich ein Programm erstelle, das eine große Anzahl von Zahlen zwischen 1 und 10^6 benötigt. Die Buckets, die die Zahlen in jedem Durchgang speichern, sind ein Array von Knoten (wobei Knoten eine von mir erstellte Struktur ist, die einen Wert und ein nächstes Knotenattribut enthält).Radix Sort implementiert in C++
Nach dem Sortieren der Zahlen in Buckets nach dem geringstwertigen Wert, habe ich das Ende eines Bucket-Punktes an den Anfang eines anderen Buckets (damit ich die gespeicherten Zahlen schnell abrufen kann, ohne die Reihenfolge zu stören). Mein Code hat keine Fehler (entweder Compilieren oder Runtime), aber ich habe eine Wand in Bezug darauf getroffen, wie ich die verbleibenden 6 Iterationen lösen werde (da ich den Zahlenbereich kenne).
Das Problem, das ich habe, ist, dass zunächst die Zahlen der RadixSort-Funktion in Form eines int-Arrays geliefert wurden. Nach der ersten Iteration der Sortierung werden die Zahlen nun im Array von Strukturen gespeichert. Gibt es eine Möglichkeit, dass ich meinen Code überarbeiten könnte, so dass 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 6 mal ausgeführt wird, bevor die vollständig sortiert 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;
}
Nichts für ungut, aber Ihr Code sieht aus wie ein gutes Beispiel dafür, wie einfache Dinge zu tun kompliziert ;-) – hirschhornsalz