Some updates on algo/csort.h and example.

1 files changed, 24 insertions, 46 deletions

diff --git a/include/stc/algo/csort.h b/include/stc/algo/csort.h
index 3d407c55..cd7cd847 100644
--- a/include/stc/algo/csort.h
+++ b/include/stc/algo/csort.h
@@ -20,12 +20,8 @@
  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
  * SOFTWARE.
  */
-#ifndef STC_CSORT_H_INCLUDED
-#define STC_CSORT_H_INCLUDED
-#include <stdint.h>
-#define c_CONCAT(a, b) a ## b
-#define c_PASTE(a, b) c_CONCAT(a, b)
-#endif
+#include <stc/priv/template.h>
+#include <stc/ccommon.h>
 
 /* Generic Quicksort in C, performs as fast as c++ std::sort().
 template params:
@@ -44,24 +40,17 @@ template params:
 #include <algorithm>
 #endif
 
-int testsort(csortval_int *a, size_t size, const char *desc) {
+void testsort(csortval_int *a, size_t size, const char *desc) {
     clock_t t = clock();
-#ifdef __cplusplus
-    printf("std::sort: ");
-    std::sort(a, a + size);
-#else
-    printf("csort: ");
     csort_int(a, size);
-#endif
     t = clock() - t;
 
     printf("%s: %zu elements sorted in %.3fms\n",
-           desc, size, t * 1000.0 / CLOCKS_PER_SEC);
-    return 0;
+           desc, size, t*1000.0/CLOCKS_PER_SEC);
 }
 
-int main(int argc, char *argv[]) {
-    size_t i, size = argc > 1 ? strtoull(argv[1], NULL, 0) : 10000000;
+int main() {
+    size_t i, size = 10000000;
     csortval_int *a = (csortval_int*)malloc(sizeof(*a) * size);
     if (a != NULL) {
         for (i = 0; i < size; i++)
@@ -69,26 +58,13 @@ int main(int argc, char *argv[]) {
         testsort(a, size, "random");
         for (i = 0; i < 20; i++) printf(" %d", a[i]);
         puts("");
-        testsort(a, size, "sorted");
-        for (i = 0; i < size; i++) a[i] = size - i;
-        testsort(a, size, "reverse sorted");
-        for (i = 0; i < size; i++) a[i] = 126735;
-        testsort(a, size, "constant");
         free(a);
     }
-    return 0;
 }*/
-#ifndef i_tag
-#define i_tag i_val
-#endif
-#ifndef i_less
-#define i_less(x, y) *x < *y
-#endif
-
 typedef i_val c_PASTE(csortval_, i_tag);
 
-static inline void c_PASTE(cisort_, i_tag)(i_val arr[], intptr_t low, intptr_t high) {
-    for (intptr_t j = low, i = low+1; i <= high; j = i, ++i) {
+static inline void c_PASTE(cisort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi) {
+    for (intptr_t j = lo, i = lo + 1; i <= hi; j = i, ++i) {
         i_val key = arr[i];
         while (j >= 0 && (i_less((&key), (&arr[j])))) {
             arr[j + 1] = arr[j];
@@ -98,30 +74,32 @@ static inline void c_PASTE(cisort_, i_tag)(i_val arr[], intptr_t low, intptr_t h
     }
 }
 
-static inline void c_PASTE(cqsort_, i_tag)(i_val arr[], intptr_t low, intptr_t high)
+static inline void c_PASTE(cqsort_, i_tag)(i_val arr[], intptr_t lo, intptr_t hi)
 {
-    intptr_t i = low, j = high;
-    i_val pivot = arr[(i + j)/2];
+    intptr_t i = lo, j = hi;
+    i_val pivot = arr[lo + (hi - lo)*7/16];
 
     while (i <= j) {
         while (i_less((&arr[i]), (&pivot))) ++i;
         while (i_less((&pivot), (&arr[j]))) --j;
         if (i <= j) {
-            i_val t = arr[i]; arr[i] = arr[j]; arr[j] = t;
+            c_SWAP(i_val, arr+i, arr+j);
             ++i; --j;
         }
     }
-    if (j > low) j - low < 65 ? c_PASTE(cisort_, i_tag)(arr, low, j)
-                              : c_PASTE(cqsort_, i_tag)(arr, low, j);
-    if (i < high) high - i < 65 ? c_PASTE(cisort_, i_tag)(arr, i, high)
-                                : c_PASTE(cqsort_, i_tag)(arr, i, high);
+    if (j - lo > hi - i) {
+        c_SWAP(intptr_t, &lo, &i);
+        c_SWAP(intptr_t, &hi, &j);
+    }
+    if (j - lo > 64) c_PASTE(cqsort_, i_tag)(arr, lo, j);
+    else if (j > lo) c_PASTE(cisort_, i_tag)(arr, lo, j);
+    if (hi - i > 64) c_PASTE(cqsort_, i_tag)(arr, i, hi);
+    else if (hi > i) c_PASTE(cisort_, i_tag)(arr, i, hi);
 }
 
-static inline void c_PASTE(csort_, i_tag)(i_val arr[], size_t elements)
+static inline void c_PASTE(csort_, i_tag)(i_val arr[], size_t n)
 {
-    elements < 65 ? c_PASTE(cisort_, i_tag)(arr, 0, (intptr_t)elements - 1)
-                  : c_PASTE(cqsort_, i_tag)(arr, 0, (intptr_t)elements - 1);
+    if (n > 64) c_PASTE(cqsort_, i_tag)(arr, 0, (intptr_t)n - 1);
+    else        c_PASTE(cisort_, i_tag)(arr, 0, (intptr_t)n - 1);
 }
-#undef i_tag
-#undef i_val
-#undef i_less
+#include <stc/priv/template.h>
\ No newline at end of file