From b3313ff01a8069592f63b18372fd0cf9e6c077bd Mon Sep 17 00:00:00 2001 From: Tyge Løvset Date: Tue, 10 Jan 2023 16:59:41 +0100 Subject: Some updates on algo/csort.h and example. --- include/stc/algo/csort.h | 70 +++++++++++++++++------------------------------- 1 file changed, 24 insertions(+), 46 deletions(-) (limited to 'include') 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 -#define c_CONCAT(a, b) a ## b -#define c_PASTE(a, b) c_CONCAT(a, b) -#endif +#include +#include /* Generic Quicksort in C, performs as fast as c++ std::sort(). template params: @@ -44,24 +40,17 @@ template params: #include #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 \ No newline at end of file -- cgit v1.2.3