I encountered a thread regarding a similar/exact same assignment from last year. It was very helpful in assuring me that what code I do have is close, if not exactly what it needs to be, here:
http://www.cplusplus.com/forum/beginner/200458/
But it doesn't address a latter portion that I am having trouble with. I don't know about that dude/dudette's assignment, but it seems almost like I am expected to recurse through the method, right? Here's the catch, the recursion is told to look at character 1, then does its thing, then calls itself passing the 2nd char to look at, then the third, and on until a certain character index is reached. Each recursive step/segment is passed the same full bin of items that you dequeue from, then test a given character to place in the correct queue "bin". So, what's the issue?
My issues are thus:
1. I don't understand how I recurse according to testChar index, and in that given recursive step, do this test not for one dequeue'ing of one item, but 37 times per recursive step, placing htem in 37 queues. I already am doing a base case and recursive call for one context, and it is my understanding that recursive functions don't have some For or While loop embeded in their operations.
2. If I dequeue an item from the bin, doesn't the bin now hold one less item? So how do I not only dequeue 37 times from the bin on the first operation, but now do so with the same bin during each recursive step, wherein the bin will be dequeue'ed until empty, call itself, then do it again until the base case is reached?
3. After all this, then the potentially hundreds of queues are supposed to be placed in one bin, or was it just the "last" recursive section that gets enqueue'ed into the bin that gets returned to radixSortAsc?
Here's where I'm at with my code. The way my binSort works now, it dequeues once, tests one character, then recurses, passing the next currChar location, so it doesn't exactly do what it needs to:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90
|
template < class T >
void RadixSort<T>::radixSortAsc(T** sort, int n, int num_chars, char (*getRadixChar) (T* st, int index))
{
//DO THIS
T* bin = new QueueLinked<T>();
for( int i = 0; i < n; i++)
{
bin[i]->enqueue( sort[i] );
}
int currChar = tolower( (*getRadixChar) (bin[0], 0) );
binSort(bin, 1, num_chars, getRadixChar);
for(int i = 0; i < number of items; i++)
{
sort[i] = bin->dequeue(); //put items in bin back in sort array
}
}
template < class T >
void RadixSort<T>::binSort(QueueLinked<T>* bin, int curr_char, int num_chars, char (*getRadixChar) (T* st, int index))
{
//DO THIS
if( !( bin->isEmpty() ) )
{
if( bin->size() != 1 )
{
if( curr_char != num_chars)
{
// This should create the necessary sorted queuelinkedd bins
QueueLinked<T>** sorted = new QueueLinked<T>*[37];
for(int i = 0; i < 37; i++)
{
bins[i] = new QueueLinked<T>();
}
// This should hold the dequeu'ed item long enough to extract a character from it.
T* currItem;
// testChar is hte char to be tested
// currIndex is for directing what bin a char pertains to
// counter is a potential variable for guaranteeing no more than 250 chars are tested
int testChar, currIndex, coounter;
testChar = tolower( (*getRadixChar) (currItem, curr_char) );
if( ( curr_char >= '33' && curr_char <= '47' ) || ( curr_char >= '58' && curr_char <= '64' )
{
// Push the curr element of sort onto bin 0 of bins;
sorted[0]->enqueue( currItem );
}
else if( testChar >= '48' && testChar <= '57' )
{
/**********************************************
Since bin 0 is for special characters, then
any 0 must be in bin 1.
Since currChar == '48' if it is a 0,
that means "int index = currChar - 47"
And we want all 9s which equal '57'
to go into bin 10. And that seems
to char-ey on as above.
**********************************************/
currIndex = testChar - 47;
sorted[currIndex]->enqueue( currItem );
}
else if( testChar >= '65' && testChar <= '90' )
{
currIndex = testChar - 54;
sorted[currIndex]->enqueue( currItem );
}
counter += 1;
// Recursive step
binSort(bin, (curr_char+1), num_chars, (*getRadixChar) (T* st, int index) );
}
}
}
}
|