DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 19

Thread: Radix Sort- sorting integers(treated as char string)

  1. #1
    Join Date
    Mar 2006
    Posts
    24

    Question 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
    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:

  2. #2
    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. #3
    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. #4
    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. #5
    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. #6
    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. #7
    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: 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 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. #8
    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. #9
    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. #10
    Join Date
    Mar 2006
    Posts
    24

    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:

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

    system("PAUSE");

  12. #12
    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. #13
    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. #14
    Join Date
    Mar 2006
    Posts
    24
    i tried pow(10.0, (i*1.0)) too.. still same error :(

  15. #15
    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:

Similar Threads

  1. Input string was not in a correct format
    By mdengler in forum ASP.NET
    Replies: 0
    Last Post: 11-26-2002, 03:32 PM
  2. Replies: 1
    Last Post: 06-05-2001, 06:12 AM
  3. VB/C Array parameters
    By Gastao Woelfert in forum VB Classic
    Replies: 2
    Last Post: 09-01-2000, 11:36 AM
  4. VB/C Array parameters
    By Gastao Woelfert in forum VB Classic
    Replies: 0
    Last Post: 09-01-2000, 08:59 AM
  5. Database problems
    By Robert Rieth in forum VB Classic
    Replies: 1
    Last Post: 04-11-2000, 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
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

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