Recursive Radix Sorting Using Queues

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) );
				
			}
		  
		}
	}
}
Last edited on
It appears no one is ever, going to respond to my question about this, and I finished my program, to the best of my ability, over two weeks ago with no insight or help provided from this forum. So, I'm going to mark this thread as solved.

Or at least I would if I was allowed to either mark this thread as solved, whereas I solved my own problems after several hours, or at the very least delete this thread. It seems I can do neither.
Last edited on
Topic archived. No new replies allowed.