COIN-OR::LEMON - Graph Library

Changeset 1844:eaa5f5b855f7 in lemon-0.x


Ignore:
Timestamp:
12/03/05 19:15:43 (19 years ago)
Author:
Balazs Dezso
Branch:
default
Phase:
public
Convert:
svn:c9d7d8f5-90d6-0310-b91f-818b3a526b0e/lemon/trunk@2403
Message:

Changed implementation and bug fix

Files:
2 edited

Legend:

Unmodified
Added
Removed
  • lemon/radix_sort.h

    r1833 r1844  
    255255  template <typename Value>
    256256  unsigned char valueByte(Value value, int byte) {
    257     return *((unsigned char *)(&value) + byte);
     257    return value >> (std::numeric_limits<unsigned char>::digits * byte);
    258258  }
    259259
     
    366366      bool dir = true;
    367367      std::copy(first, last, buffer);
    368       for (int i = 0; i < sizeof(Value); ++i) {
     368      for (int i = 0; i < (int)sizeof(Value); ++i) {
    369369        if (dir) {
    370           counterIntroSort(buffer, buffer + length, buffer + length,
    371                            i, functor);
     370          counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
    372371        } else {
    373           counterIntroSort(buffer + length, buffer + 2 * length, buffer,
    374                            i, functor);
     372          counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
    375373        }
    376374        dir = !dir;
     
    426424  /// in the right order in \c O(n) time. The algorithm sorts the container
    427425  /// by each bytes in forward direction which sorts the container by the
    428   /// whole value. This way, let be
    429   /// \c c the maximal capacity and \c n the number of the items in
     426  /// whole value. This way, let be \c c the maximal capacity of the integer
     427  /// type and \c n the number of the items in
    430428  /// the container, the time complexity of the algorithm \c O(log(c)*n)
    431429  /// and the additional space complexity is \c O(n).
  • test/radix_sort_test.cc

    r1833 r1844  
    1616
    1717void checkRadixSort() {
    18   int n = 10000;
    19   vector<int> data1(n), data2(n);
    20   for (int i = 0; i < n; ++i) {
    21     data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
    22   }
    23   radixSort(data1.begin(), data1.end());
    24   sort(data2.begin(), data2.end());
    25   for (int i = 0; i < n; ++i) {
    26     check(data1[i] == data2[i], "Test failed");
     18  {
     19    int n = 10000;
     20    vector<int> data1(n), data2(n);
     21    for (int i = 0; i < n; ++i) {
     22      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
     23    }
     24    radixSort(data1.begin(), data1.end());
     25    sort(data2.begin(), data2.end());
     26    for (int i = 0; i < n; ++i) {
     27      check(data1[i] == data2[i], "Test failed");
     28    }
     29  } {
     30    int n = 10000;
     31    vector<unsigned char> data1(n), data2(n);
     32    for (int i = 0; i < n; ++i) {
     33      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
     34    }
     35    radixSort(data1.begin(), data1.end());
     36    sort(data2.begin(), data2.end());
     37    for (int i = 0; i < n; ++i) {
     38      check(data1[i] == data2[i], "Test failed");
     39    }
    2740  }
    2841}
     
    3043
    3144void checkCounterSort() {
    32   int n = 10000;
    33   vector<int> data1(n), data2(n);
    34   for (int i = 0; i < n; ++i) {
    35     data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
    36   }
    37   counterSort(data1.begin(), data1.end());
    38   sort(data2.begin(), data2.end());
    39   for (int i = 0; i < n; ++i) {
    40     check(data1[i] == data2[i], "Test failed");
     45  {
     46    int n = 10000;
     47    vector<int> data1(n), data2(n);
     48    for (int i = 0; i < n; ++i) {
     49      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
     50    }
     51    counterSort(data1.begin(), data1.end());
     52    sort(data2.begin(), data2.end());
     53    for (int i = 0; i < n; ++i) {
     54      check(data1[i] == data2[i], "Test failed");
     55    }
     56  } {
     57    int n = 10000;
     58    vector<unsigned char> data1(n), data2(n);
     59    for (int i = 0; i < n; ++i) {
     60      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
     61    }
     62    counterSort(data1.begin(), data1.end());
     63    sort(data2.begin(), data2.end());
     64    for (int i = 0; i < n; ++i) {
     65      check(data1[i] == data2[i], "Test failed");
     66    }
    4167  }
    4268}
Note: See TracChangeset for help on using the changeset viewer.