Changeset 1844:eaa5f5b855f7 in lemon0.x
 Timestamp:
 12/03/05 19:15:43 (15 years ago)
 Branch:
 default
 Phase:
 public
 Convert:
 svn:c9d7d8f590d60310b91f818b3a526b0e/lemon/trunk@2403
 Files:

 2 edited
Legend:
 Unmodified
 Added
 Removed

lemon/radix_sort.h
r1833 r1844 255 255 template <typename Value> 256 256 unsigned char valueByte(Value value, int byte) { 257 return *((unsigned char *)(&value) +byte);257 return value >> (std::numeric_limits<unsigned char>::digits * byte); 258 258 } 259 259 … … 366 366 bool dir = true; 367 367 std::copy(first, last, buffer); 368 for (int i = 0; i < sizeof(Value); ++i) {368 for (int i = 0; i < (int)sizeof(Value); ++i) { 369 369 if (dir) { 370 counterIntroSort(buffer, buffer + length, buffer + length, 371 i, functor); 370 counterIntroSort(buffer, buffer + length, buffer + length, i, functor); 372 371 } else { 373 counterIntroSort(buffer + length, buffer + 2 * length, buffer, 374 i, functor); 372 counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor); 375 373 } 376 374 dir = !dir; … … 426 424 /// in the right order in \c O(n) time. The algorithm sorts the container 427 425 /// by each bytes in forward direction which sorts the container by the 428 /// whole value. This way, let be 429 /// \c c the maximal capacityand \c n the number of the items in426 /// 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 430 428 /// the container, the time complexity of the algorithm \c O(log(c)*n) 431 429 /// and the additional space complexity is \c O(n). 
test/radix_sort_test.cc
r1833 r1844 16 16 17 17 void 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 } 27 40 } 28 41 } … … 30 43 31 44 void 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 } 41 67 } 42 68 }
Note: See TracChangeset
for help on using the changeset viewer.