Thread: Bucket/Radix Sort with Vectors Broken!

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    6

    Bucket/Radix Sort with Vectors Broken!

    I have this bucket/radix sort i'm hacking away at and i can't make it work at all. I am trying to implement the algorithm to sort it in ascending order from A through Z for words in a struct. I'm honestly stuck!

    Code:
    //the struct
    struct Wrd {
    	int wordCounter;				//number of times a word exists
    	string theword;                                   //the actual word
    };
    
    //the sort
    void bucketSort(vector<Wrd>& V, int start, int stop, int pos){
        int i, j, k, index;
        vector<Wrd> buckets (27);
        // bin 26 is reserved for strings shorter than the current length
    
        // push all of the V into the right bins
        for(start = 0; start < stop; start++){
             if(V[i].theword.size() <= pos){
    	     buckets[26].push_back(V[i].theword);
    	 } else {
    	     index = int(V[i].theword[pos] -'a');
                 buckets[index].push_back(V[i].theword);
    	 }
        }
    
        // take them out of the bins and put them back into the list
        j = 0;
        for(i = 0;i <= 26; i++) {
            for(k = buckets[start]; k! = buckets[stop]; k++) {
    	    V[j].theword = *k;
    	    j++;
    	}
        }
    }
    
    //the call
             bubbleSort(V, 0, size);

  2. #2
    Registered User
    Join Date
    Oct 2005
    Posts
    38
    Code:
    typedef struct{
    
         int wordCounter;
         string theWord;
    
    }Wrd;
    [NOTE] Your original version was correct on the definition of the struct, just my bias to declare structs in the manner mentioned above (its a carry over from c)

    also, why are you passing start to the function when you immediately set it to zero in the loop (it doesn't matter what you pass to the function with your definition, so why not create it as a local variable?)


    you have also declared k as type int, however buckets is a vector of Wrd objects, so accesing the ith element returns type Wrd, not int.
    Last edited by ExxNuker; 11-17-2005 at 02:38 PM.

  3. #3
    Registered User
    Join Date
    Jan 2005
    Posts
    7,366
    Code:
    typedef struct{
    
         int wordCounter;
         string theWord;
    
    }Wrd;
    That isn't necessary in C++. TheSpoiledMilk's version was correct.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Straight Insertion Sort function problem
    By StaticKyle in forum C++ Programming
    Replies: 6
    Last Post: 05-12-2008, 04:03 AM
  2. How properly get data out of vectors of templates?
    By 6tr6tr in forum C++ Programming
    Replies: 4
    Last Post: 04-15-2008, 10:35 AM
  3. Sort two vectors in the same order
    By jw232 in forum C++ Programming
    Replies: 2
    Last Post: 03-08-2008, 05:49 PM
  4. Using Vectors (cont) - Sort Problem
    By clegs in forum C++ Programming
    Replies: 2
    Last Post: 09-17-2007, 06:31 AM
  5. Shell Sort with Vectors Problem
    By TheSpoiledMilk in forum C++ Programming
    Replies: 4
    Last Post: 11-22-2005, 03:05 PM