Changeset 1844:eaa5f5b855f7 in lemon-0.x

Timestamp:

12/03/05 19:15:43 (18 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:

• lemon/radix_sort.h (modified) (3 diffs)
• test/radix_sort_test.cc (modified) (2 diffs)

lemon/radix_sort.h

@@ -255 +255 @@
   template <typename Value>
   unsigned char valueByte(Value value, int byte) {
-    return *((unsigned char *)(&value) + byte);
+    return value >> (std::numeric_limits<unsigned char>::digits * byte);
   }
 
@@ -366 +366 @@
       bool dir = true;
       std::copy(first, last, buffer);
-      for (int i = 0; i < sizeof(Value); ++i) {
+      for (int i = 0; i < (int)sizeof(Value); ++i) {
         if (dir) {
-          counterIntroSort(buffer, buffer + length, buffer + length, 
-                           i, functor);
+          counterIntroSort(buffer, buffer + length, buffer + length, i, functor);
         } else {
-          counterIntroSort(buffer + length, buffer + 2 * length, buffer, 
-                           i, functor);
+          counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor);
         }
         dir = !dir;
@@ -426 +424 @@
   /// in the right order in \c O(n) time. The algorithm sorts the container
   /// by each bytes in forward direction which sorts the container by the
-  /// whole value. This way, let be
-  /// \c c the maximal capacity and \c n the number of the items in
+  /// whole value. This way, let be \c c the maximal capacity of the integer 
+  /// type and \c n the number of the items in
   /// the container, the time complexity of the algorithm \c O(log(c)*n)
   /// and the additional space complexity is \c O(n).

test/radix_sort_test.cc

@@ -16 +16 @@
 
 void checkRadixSort() {
-  int n = 10000;
-  vector<int> data1(n), data2(n);
-  for (int i = 0; i < n; ++i) {
-    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
-  }
-  radixSort(data1.begin(), data1.end());
-  sort(data2.begin(), data2.end());
-  for (int i = 0; i < n; ++i) {
-    check(data1[i] == data2[i], "Test failed");
+  {
+    int n = 10000;
+    vector<int> data1(n), data2(n);
+    for (int i = 0; i < n; ++i) {
+      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+    }
+    radixSort(data1.begin(), data1.end());
+    sort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    }
+  } {
+    int n = 10000;
+    vector<unsigned char> data1(n), data2(n);
+    for (int i = 0; i < n; ++i) {
+      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
+    }
+    radixSort(data1.begin(), data1.end());
+    sort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    }
   }
 }
@@ -30 +43 @@
 
 void checkCounterSort() {
-  int n = 10000;
-  vector<int> data1(n), data2(n);
-  for (int i = 0; i < n; ++i) {
-    data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
-  }
-  counterSort(data1.begin(), data1.end());
-  sort(data2.begin(), data2.end());
-  for (int i = 0; i < n; ++i) {
-    check(data1[i] == data2[i], "Test failed");
+  {
+    int n = 10000;
+    vector<int> data1(n), data2(n);
+    for (int i = 0; i < n; ++i) {
+      data1[i] = data2[i] = (int)(1000 * (rand() / (RAND_MAX + 1.0))) - 500;
+    }
+    counterSort(data1.begin(), data1.end());
+    sort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    } 
+  } {
+    int n = 10000;
+    vector<unsigned char> data1(n), data2(n);
+    for (int i = 0; i < n; ++i) {
+      data1[i] = data2[i] = (int)(200 * (rand() / (RAND_MAX + 1.0)));
+    }
+    counterSort(data1.begin(), data1.end());
+    sort(data2.begin(), data2.end());
+    for (int i = 0; i < n; ++i) {
+      check(data1[i] == data2[i], "Test failed");
+    } 
   }
 }