
Radix Sort sorting integers(treated as char string)
i need to sort integers using Radix sort... :rolleyes:
To start with the skeleton code, I've used Standard Template Library class queue..
The integer list should be stored in a queue. The grouping procee scans the input list and adds an integer into a respective sublist according to the digit value of the integer.
To get the single digit of an integer, I should use / and % operator,
e.g 1234 % 10 = 4, (1234/10)%10 = 3
Error conditions : I need not check and address any invalid input.
Sample output :
Please input the maximum number of digits:
3
Please input the number of the integers to sort:
4
Please input the integer list:
023 231 523 001
Output:
231 001 023 523
001 023 523 231
001 023 231 523
the above is my question... and i have started with my program.. can anybody help me step by step with it..???
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int numOfMaxBits, numOfInt, i, j;
cout << "Please input the maximum number of the digits:" << endl;
cin >> numOfMaxBits;
cout << "Please input the number of the integers to sort:" << endl;
cin >> numOfInt;
// input the list of integers
queue<int> mainQ;
cout << "Please input the integer list:" << endl;
for (i=0; i<numOfInt; i++) {
}
// the iterative process
// should use 10 subqueues in the following grouping and
// combining process, i.e., queue<int> subQ[10];
cout << "Output:" << endl;
for (i=0; i<numOfMaxBits; i++) {
// grouping into sunQ
for (j=0;j < numOfInt; j++) {
}
// combing subQ into mainQ
for (j=0; j<10;j++) {
// output the combining result
}
cout << endl;
}
return 0;
}
thats my prog.. using subqueues in grouping and combining is quite confusing.. :confused:

You have stated the pseudocode for your allocation out to the various queue buckets based on the value of the digit position of interest.
you'll have an outer loop which is counting up  "i = 0 to numOfMaxBits"  to the number of positions
you have an inner loop which is counting up  "j = 0 to numOfInt"  to the number of integers you are sorting  but, since you are using queues, why not use the empty() method  while(!queue.empty() ) ...
you determine the value of the position of interest by dividing by 10^i and taking modulo of 10 of the result
so, inside your "second loop", you pop a value off the main queue, get the value of the position of interest in the integer you just popped off, push the integer to the queue of that position's value
when you've read them all into the subqueues (the main queue is empty()), start from subqueue[0] and pop the values and push them immediately back into the main queue until that subqueue is empty(), move on to the next subqueue, and so on until you have emptied subqueue[9].
Last edited by nspils; 03102006 at 09:26 AM.

heya i dun get it.. can u explain with examples?? sorry.. ok. suppose i input 398, 54, 2, 71. now i pop 71 out from the main menu.. my value (in the position of interestin this case) is 1. So u mean i have to push the number 7 to the next queue??? nd then?? sorry cannot get u... hope u have the time to explain with an example!!!thx
:)

So, we are sorting 398, 54, 2, 71.
You push 398 into subQ[8], push 54 into subQ[4], 2 into subQ[2], 71 into subQ[1]. mainQ is empty() so we now read values back into mainQ.
now, we have nothing in subQ[0], have 71 in subQ[1] so that is popped off subQ[1] and pushed back into mainQ and subQ[1] is empty(), so we move to subQ[2] which contains 2 so we pop 2 off that queue and push it into mainQ, etc. so we end up with mainQ having 71,2,54,398
then we move to the second digits  71 is popped off mainQ and pushed into subQ[7], 2 is pushed into subQ[0], 54 is pushed into subQ[5], 398 into subQ[9]. mainQ is empty(), so we start reading from the subQs ... 2, then 54, then 71, then 398 so mainQ has 2, 54, 71, 398
we now move to the third digit ... 2, 54, and 71 will remain in order, all in subQ[0] since we are pushing from the back and reading off the top ... and 398 will be in subQ[3]. mainQ is empty so we pop off the top of the subQs in order ...
and we're done
Last edited by nspils; 03112006 at 03:33 PM.

not getting it sorted!!!!
hey i wrote a program but i'm not getting the decired sorted output.. y?? wats wrong in my prog??hope u can correct my mistake!! thxxxxx..
#include <iostream>
20 #include <queue>
21
22 using namespace std;
23
24 int main()
25 {
26 int numOfMaxBits, numOfInt, i, j, k, p;
27
28 cout << "Please input the maximum number of the digits:" << endl;
29 cin >> numOfMaxBits;
30
31 cout << "Please input the number of the integers to sort:" << endl;
32 cin >> numOfInt;
33
34 // input the list of integers
35 queue<int> mainQ;
36 int number;
37
38 cout << "Please input the integer list:" << endl;
39 for (i=0; i<numOfInt; i++) {
40 cin >> number;
41 mainQ.push(number);
42 }
43 // the iterative process
44 // may use 10 subqueues in the following grouping and
45 // combining process, i.e., queue<int> subQ[10];
46 cout << "Output:" << endl;
47
48 for (i=0; i<numOfMaxBits; i++) {
49 // grouping into subQ
50 queue<int> subQ[10];
51
52 for (j=0; j < numOfInt; j++) {
53 for (k=0; k<10; k++){
54 p = (mainQ.front()/10^k)%10;
55 subQ[p].push(mainQ.front());
56 mainQ.pop();
57 }
58 }
59
60 // combing subQ into mainQ
61 for (j=0; j<10;j++) {
62 // output the combining result
63 while (!subQ[j].empty())
64 {
65 mainQ.push(subQ[j].front());
66 cout << " " << subQ[j].front();
67 subQ[j].pop();
68 }
69 }
70
71
72 cout << endl;
73 }
74 return 0;
75 }

Take a look at the scope of your declaration of subQ[].
I think the function can be written as:
Code:
queue<int> subQ[10];
for (i=0; i<numOfMaxBits; i++)
{
// disbursing elements of mainQ to the subQs
while( !mainQ.empty() )
{
p = (mainQ.front()/10^i)%10;
subQ[p].push( mainQ.pop() );
}
// combining elements of subQs into mainQ
for( j=0; j<10; ++j )
{
while( !subQ[j].empty() )
{
cout << " " << subQ[j].front();
mainQ.push( subQ[j].pop() );
}
}
cout << endl;
}

hey i have a doubt in ur code!!! i think pop is a void function..
i'm getting the following errors when i compile urs..
where is the prob?
radixSort.cpp: In function `int main()':
radixSort.cpp:56: invalid use of void expression
radixSort.cpp:67: invalid use of void expression
do u think i shud use front instead of pop?? but wen i tried with front i got the foll error:
radixSort.cpp: In function `int main()':
radixSort.cpp:69: request for member `pop' in `subQ', which is of nonaggregate type `queue<int,deque<int,allocator<int>,0> >[10]'
now i have another doubt!!! will 10^i work?? is power function recognised ?? does it work?? or shud i jus multiply it by 10 each time by initialising a number to 1???

pop and front are the same, in that they both return the first element of the queue  front just leaves it in the queue, pop removes it. What is happening is that nothing has been put into the subqueues ...
I think you have found a logical explanation  the determination of 10 to the ith power  I forgot about that:
import the cmath library
use pow(10, i) to calculate the power function
so, (mainQ.front()/10^i) becomes (mainQ.front()/pow(10, i))
Does that work?

I did a "quick and dirty" based upon your code ... get a warning because pow takes doubles or floats rather than an int ... but the code works fine ... You were right about the need to push the front(), then pop() ... I guess I've been coding in Java for so long it has clouded my (unverified by looking at Dinkumware's STL documentation) recollection of the STL:
Code:
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <queue>
using namespace std;
int main()
{
int numOfMaxBits, numOfInt, i, j, p;
cout << "Please input the maximum number of the digits:" << endl;
cin >> numOfMaxBits;
cout << "Please input the number of the integers to sort:" << endl;
cin >> numOfInt;
// input the list of integers
queue<int> mainQ;
int number;
cout << "Please input the integer list:" << endl;
for (i=0; i<numOfInt; i++)
{
cout << "Add an integer to the list: " << endl;
cin >> number;
mainQ.push(number);
}
// the iterative process
// may use 10 subqueues in the following grouping and
// combining process, i.e., queue<int> subQ[10];
cout << "Output:" << endl;
queue<int> subQ[10];
for (i=0; i<numOfMaxBits; ++i)
{
// disbursing elements of mainQ to the subQs
while( !mainQ.empty() )
{
p = (mainQ.front()/pow(10.0,i));
p = p%10;
subQ[p].push( mainQ.front() );
mainQ.pop();
}
// combining elements of subQs into mainQ
for( j=0; j<10; ++j )
{
while( !subQ[j].empty() )
{
cout << " " << subQ[j].front();
mainQ.push( subQ[j].front() );
subQ[j].pop();
}
}
cout << endl;
}
system("PAUSE");
return 0;
}
The only input checking I would suggest is making sure that the input is no larger than the number of digits you wanted  that the input is smaller than 10 to the power of numOfMaxBits ...
Last edited by nspils; 03142006 at 09:54 PM.

error!!!
i'm getting the following error when i run your code
radixSort.cpp: In function `int main()':
radixSort.cpp:57: warning: assignment to `int' from `double'
and the 57th line is this
p = (mainQ.front()/pow(10.0,i));
wats wrong?? i know pow accepts double but ... :confused:

whats the purpose of the following line?
system("PAUSE");

I wrote that as a console application using DevC++, and the command System("PAUSE") will hold the DOS window open so I can see the results of execution. The CodeWarrior compiler does not need it, but DevC++ does.
I was getting the warning, too, but the program ran. "P" is declared to be an int. The value being assigned to it is a double value. You "lose" something when you cast from a double to an int. The compiler is just telling you that you are losing something  do you really want to do it ...

wanna do it
yes i really wanna do it....... :p
if p is declared double, i wont get the correct output right??? anyways, i dint get it correctly.. i know i wont... hehe...
so how do i correct the error??

i tried pow(10.0, (i*1.0)) too.. still same error :(

i tried (int)(pow(10.0,(i*1.0))) also
sint get any error but i got leading 0's ... yy??? cannot handle them :confused:
Similar Threads

By mdengler in forum ASP.NET
Replies: 0
Last Post: 11262002, 03:32 PM

By Fred Mayes in forum Java
Replies: 1
Last Post: 06052001, 06:12 AM

By Gastao Woelfert in forum VB Classic
Replies: 2
Last Post: 09012000, 11:36 AM

By Gastao Woelfert in forum VB Classic
Replies: 0
Last Post: 09012000, 08:59 AM

By Robert Rieth in forum VB Classic
Replies: 1
Last Post: 04112000, 03:21 AM
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Development Centers
 Android Development Center
 Cloud Development Project Center
 HTML5 Development Center
 Windows Mobile Development Center
