We're a community of 1077K IT Pros here for help, advice, solutions, professional growth and fun. Join us!
1,076,194 Members — Technology Publication meets Social Media
Username:
Password:
Lost login information?
Start New Discussion Reply to this Discussion

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.

1
Contributor
1
Reply
3 Hours
Discussion Span
1 Year Ago
Last Updated
2
Views
Question
Answered
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

This question has already been solved: Start a new discussion instead

Post: Markdown Syntax: Formatting Help
 
You
 
© 2013 DaniWeb® LLC
Page rendered in 0.0707 seconds using 2.69MB