home *** CD-ROM | disk | FTP | other *** search
/ QBasic & Borland Pascal & C / Delphi5.iso / C / BC_502 / STDLIB.PAK / RADIX.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-06  |  1.8 KB  |  68 lines
  1. /**************************************************************************
  2.  *
  3.  * radix.cpp - radix sort program.  Section 7.3
  4.  *
  5.  * $Id: radix.cpp,v 1.3 1995/08/29 19:02:16 oberg Exp $
  6.  *
  7.  * $$RW_INSERT_HEADER "slyrs.cpp"
  8.  *
  9.  **************************************************************************/
  10.  
  11. # include <deque>
  12. # include <list>
  13. # include <vector>
  14. # include <algorithm>
  15. # include <numeric>
  16.  
  17. # include <iostream.h>
  18. using namespace std;
  19.  
  20. class copyIntoBuckets {
  21. public:
  22.     copyIntoBuckets(int d, vector< deque<unsigned int> > & b, bool & f)
  23.         : divisor(d), buckets(b), flag(f) {}
  24.     int divisor;
  25.     vector< deque<unsigned int> > & buckets;
  26.     bool & flag;
  27.     void operator () (unsigned int v)
  28.             {    int index = (v / divisor) % 10;
  29.                 // flag is set to true if any bucket
  30.                 // other than zeroth is used
  31.                 if (index) flag = true;
  32.                 buckets[index].push_back(v);
  33.             }
  34. };
  35.  
  36. list<unsigned int>::iterator listCopy(list<unsigned int>::iterator c, deque<unsigned int> & lst)
  37. {
  38.     return copy(lst.begin(), lst.end(), c);
  39. }
  40.  
  41. void radixSort(list<unsigned int> & values)
  42. {
  43.     bool flag = true;
  44.     int divisor = 1;
  45.     
  46.     while (flag) {
  47.         vector< deque<unsigned int> > buckets(10);
  48.         flag = false;
  49.         for_each(values.begin(), values.end(),
  50.             copyIntoBuckets(divisor, buckets, flag));
  51.         accumulate(buckets.begin(), buckets.end(), values.begin(), listCopy);
  52.         divisor *= 10;
  53.         copy(values.begin(), values.end(), ostream_iterator<int>(cout, " ")), cout << endl;
  54.         }
  55. }
  56.  
  57. int main() {
  58.     cout << "Radix sort program"  << endl;
  59.     int data[] = {624, 852, 426, 987, 269, 146, 415, 301, 730, 78, 593};
  60.     list<unsigned int> values(11);
  61.     copy(data, data + 11, values.begin());
  62.     radixSort(values);
  63.     copy(values.begin(), values.end(), ostream_iterator<int>(cout, " ")), cout << endl;
  64.  
  65.     cout << "End radix sort program" << endl;
  66.     return 0;    
  67. }
  68.