Don't use negative p index in quicksort This also fixes a harmless off-by-one error when moving the equal elements.
Project: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/repo Commit: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/commit/67fb2ea4 Tree: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/tree/67fb2ea4 Diff: http://git-wip-us.apache.org/repos/asf/lucy-clownfish/diff/67fb2ea4 Branch: refs/heads/master Commit: 67fb2ea43da223421b0f38279f7866eaa1901672 Parents: ab88039 Author: Nick Wellnhofer <[email protected]> Authored: Sun Apr 26 17:57:05 2015 +0200 Committer: Nick Wellnhofer <[email protected]> Committed: Sun Apr 26 19:45:01 2015 +0200 ---------------------------------------------------------------------- runtime/core/Clownfish/Util/SortUtils.c | 16 ++++++++-------- 1 file changed, 8 insertions(+), 8 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/lucy-clownfish/blob/67fb2ea4/runtime/core/Clownfish/Util/SortUtils.c ---------------------------------------------------------------------- diff --git a/runtime/core/Clownfish/Util/SortUtils.c b/runtime/core/Clownfish/Util/SortUtils.c index 2c0eb54..e1fd72e 100644 --- a/runtime/core/Clownfish/Util/SortUtils.c +++ b/runtime/core/Clownfish/Util/SortUtils.c @@ -282,8 +282,8 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right, = SI_choose_pivot4(elems, left, right, compare, context); int32_t i = left; int32_t j = right - 1; - int32_t p = left - 1; - int32_t q = right; + int32_t p = left; + int32_t q = right - 1; if (right <= left) { return; } @@ -323,12 +323,12 @@ S_qsort4(FOUR_BYTE_TYPE *elems, int32_t left, int32_t right, // Move any elements which test as "equal" to the pivot to the outside // edges of the array. if (comparison2 == 0) { - p++; SI_exchange4(elems, p, i); + p++; } if (comparison1 == 0) { - q--; SI_exchange4(elems, j, q); + q--; } i++; @@ -390,8 +390,8 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right, = SI_choose_pivot8(elems, left, right, compare, context); int32_t i = left; int32_t j = right - 1; - int32_t p = left - 1; - int32_t q = right; + int32_t p = left; + int32_t q = right - 1; if (right <= left) { return; } @@ -431,12 +431,12 @@ S_qsort8(EIGHT_BYTE_TYPE *elems, int32_t left, int32_t right, // Move any elements which test as "equal" to the pivot to the outside // edges of the array. if (comparison2 == 0) { - p++; SI_exchange8(elems, p, i); + p++; } if (comparison1 == 0) { - q--; SI_exchange8(elems, j, q); + q--; } i++;
