Radix Sort Efficency Help?
So, I'm back once again. This week I'm having issues with efficiency in a Radix Sort Algorithm. From what I understand this is the foundation of this algorithm.
What operations might be costing me? For the basics I suppose I do understand push_ back being costly having to copy the entire array.
My code:
for(int i=0; i<10; i++){
// goes through from least to most significant
for(int j=0; j<V.size(); j++){
temp=((V[j]/PowValue) % 10);//finds which bucket the value should be placed under
Buckets[temp].push_back(V[j]); //places value into correct bucket
}
//Places values from buckets back into the original vector array
for(int k=0; k<Buckets.size(); k++){
for(int l=0; l<Buckets[k].size(); l++){
V[PosCount]=Buckets[k][l];
PosCount++;
}
Buckets[k].clear();
}
PosCount=0;
PowValue=PowValue*10;
}
Once again, any help, suggestion, etc. would be much appreciated.
Related Article: Radix sort
is a C++ discussion thread by aaal that has 1 reply and was last updated 6 months ago.
butler273
Newbie Poster
10 posts since Apr 2011
Reputation Points: 10
Solved Threads: 0
Skill Endorsements: 0
Question Self-Answered as of 1 Year Ago
So, I'm back once again. This week I'm having issues with efficiency in a Radix Sort Algorithm. From what I understand this is the foundation of this algorithm.
What operations might be costing me? For the basics I suppose I do understand push_ back being costly having to copy the entire array.
My code:
for(int i=0; i<10; i++){
// goes through from least to most significant
for(int j=0; j<V.size(); j++){
temp=((V[j]/PowValue) % 10);//finds which bucket the value should be placed under
Buckets[temp].push_back(V[j]); //places value into correct bucket
}
//Places values from buckets back into the original vector array
for(int k=0; k<Buckets.size(); k++){
for(int l=0; l<Buckets[k].size(); l++){
V[PosCount]=Buckets[k][l];
PosCount++;
}
Buckets[k].clear();
}
PosCount=0;
PowValue=PowValue*10;
}
Once again, any help, suggestion, etc. would be much appreciated.
Nevermind this
butler273
Newbie Poster
10 posts since Apr 2011
Reputation Points: 10
Solved Threads: 0
Skill Endorsements: 0