lucy-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From nwelln...@apache.org
Subject [12/22] lucy-clownfish git commit: Don't use negative i index in quicksort
Date Wed, 29 Apr 2015 19:55:13 GMT
Don't use negative i index in quicksort


Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo
Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/ab880391
Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/ab880391
Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/ab880391

Branch: refs/heads/master
Commit: ab880391a19533eed96a7b09a26a4cd29d403b29
Parents: 87ffd92
Author: Nick Wellnhofer <wellnhofer@aevum.de>
Authored: Sun Apr 26 17:54:39 2015 +0200
Committer: Nick Wellnhofer <wellnhofer@aevum.de>
Committed: Sun Apr 26 19:45:01 2015 +0200

----------------------------------------------------------------------
 runtime/core/Clownfish/Util/SortUtils.c | 22 ++++++++++++++--------
 1 file changed, 14 insertions(+), 8 deletions(-)
----------------------------------------------------------------------


http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/ab880391/runtime/core/Clownfish/Util/SortUtils.c
----------------------------------------------------------------------
diff --git a/runtime/core/Clownfish/Util/SortUtils.c b/runtime/core/Clownfish/Util/SortUtils.c
index a0a4ca3..2c0eb54 100644
--- a/runtime/core/Clownfish/Util/SortUtils.c
+++ b/runtime/core/Clownfish/Util/SortUtils.c
@@ -280,8 +280,8 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right,
          CFISH_Sort_Compare_t compare, void *context) {
     FOUR_BYTE_TYPE *const pivot
         = SI_choose_pivot4(elems, left, right, compare, context);
-    int32_t i = left - 1;
-    int32_t j = right;
+    int32_t i = left;
+    int32_t j = right - 1;
     int32_t p = left - 1;
     int32_t q = right;
 
@@ -298,19 +298,19 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right,
         // Find an element from the left that is greater than or equal to the
         // pivot (i.e. that should move to the right).
         while (1) {
-            i++;
             comparison1 = compare(context, elems + i, pivot);
             if (comparison1 >= 0) { break; }
             if (i == right)       { break; }
+            i++;
         }
 
         // Find an element from the right that is less than or equal to the
         // pivot (i.e. that should move to the left).
         while (1) {
-            j--;
             comparison2 = compare(context, elems + j, pivot);
             if (comparison2 <= 0) { break; }
             if (j == left)        { break; }
+            j--;
         }
 
         // Bail out of loop when we meet in the middle.
@@ -330,6 +330,9 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right,
             q--;
             SI_exchange4(elems, j, q);
         }
+
+        i++;
+        j--;
     }
 
     /* Move "equal" elements from the outside edges to the center.
@@ -385,8 +388,8 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right,
          CFISH_Sort_Compare_t compare, void *context) {
     EIGHT_BYTE_TYPE *const pivot
         = SI_choose_pivot8(elems, left, right, compare, context);
-    int32_t i = left - 1;
-    int32_t j = right;
+    int32_t i = left;
+    int32_t j = right - 1;
     int32_t p = left - 1;
     int32_t q = right;
 
@@ -403,19 +406,19 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right,
         // Find an element from the left that is greater than or equal to the
         // pivot (i.e. that should move to the right).
         while (1) {
-            i++;
             comparison1 = compare(context, elems + i, pivot);
             if (comparison1 >= 0) { break; }
             if (i == right)       { break; }
+            i++;
         }
 
         // Find an element from the right that is less than or equal to the
         // pivot (i.e. that should move to the left).
         while (1) {
-            j--;
             comparison2 = compare(context, elems + j, pivot);
             if (comparison2 <= 0) { break; }
             if (j == left)        { break; }
+            j--;
         }
 
         // Bail out of loop when we meet in the middle.
@@ -435,6 +438,9 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right,
             q--;
             SI_exchange8(elems, j, q);
         }
+
+        i++;
+        j--;
     }
 
     /* Move "equal" elements from the outside edges to the center.


Mime
View raw message