DevX Home Today's Headlines   Articles Archive   Tip Bank   Forums

1. Registered User
Join Date
Mar 2006
Posts
24

## 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 sub-list 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
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:

2. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 sub-queues (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; 03-10-2006 at 09:26 AM.

3. Registered User
Join Date
Mar 2006
Posts
24
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 interest-in 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
:)

4. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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; 03-11-2006 at 03:33 PM.

5. Registered User
Join Date
Mar 2006
Posts
24

## 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 }

6. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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;
}```

7. Registered User
Join Date
Mar 2006
Posts
24
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: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:69: request for member `pop' in `subQ', which is of non-aggregate 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???

8. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 i-th 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?

9. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 (un-verified 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; 03-14-2006 at 09:54 PM.

10. Registered User
Join Date
Mar 2006
Posts
24

## error!!!

i'm getting the following error when i run your code

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:

11. Registered User
Join Date
Mar 2006
Posts
24
whats the purpose of the following line?

system("PAUSE");

12. Senior Member
Join Date
Dec 2004
Location
San Bernardino County, California
Posts
1,468
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 ...

13. Registered User
Join Date
Mar 2006
Posts
24

## 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??

14. Registered User
Join Date
Mar 2006
Posts
24
i tried pow(10.0, (i*1.0)) too.. still same error :(

15. Registered User
Join Date
Mar 2006
Posts
24
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:

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

 FAQ Latest Articles Java .NET XML Database Enterprise