From de034a8fae918b4a3441e5e7b8b4678168233518 Mon Sep 17 00:00:00 2001 From: Attractive Chaos Date: Thu, 13 Jan 2011 12:25:08 -0500 Subject: [PATCH] Added ksort.h --- ksort.h | 269 ++++++++++++++++++ ksort_test.c | 84 ++++++ ksort_test.cc | 751 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1104 insertions(+) create mode 100644 ksort.h create mode 100644 ksort_test.c create mode 100644 ksort_test.cc diff --git a/ksort.h b/ksort.h new file mode 100644 index 0000000..4b79124 --- /dev/null +++ b/ksort.h @@ -0,0 +1,269 @@ +/* The MIT License + + Copyright (c) 2008, 2009 by Heng Li + + Permission is hereby granted, free of charge, to any person obtaining + a copy of this software and associated documentation files (the + "Software"), to deal in the Software without restriction, including + without limitation the rights to use, copy, modify, merge, publish, + distribute, sublicense, and/or sell copies of the Software, and to + permit persons to whom the Software is furnished to do so, subject to + the following conditions: + + The above copyright notice and this permission notice shall be + included in all copies or substantial portions of the Software. + + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, + EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF + MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND + NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS + BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN + ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN + CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE + SOFTWARE. +*/ + +/* + 2008-11-16 (0.1.4): + + * Fixed a bug in introsort() that happens in rare cases. + + 2008-11-05 (0.1.3): + + * Fixed a bug in introsort() for complex comparisons. + + * Fixed a bug in mergesort(). The previous version is not stable. + + 2008-09-15 (0.1.2): + + * Accelerated introsort. On my Mac (not on another Linux machine), + my implementation is as fast as std::sort on random input. + + * Added combsort and in introsort, switch to combsort if the + recursion is too deep. + + 2008-09-13 (0.1.1): + + * Added k-small algorithm + + 2008-09-05 (0.1.0): + + * Initial version + +*/ + +#ifndef AC_KSORT_H +#define AC_KSORT_H + +#include +#include + +typedef struct { + void *left, *right; + int depth; +} ks_isort_stack_t; + +#define KSORT_SWAP(type_t, a, b) { register type_t t=(a); (a)=(b); (b)=t; } + +#define KSORT_INIT(name, type_t, __sort_lt) \ + void ks_mergesort_##name(size_t n, type_t array[], type_t temp[]) \ + { \ + type_t *a2[2], *a, *b; \ + int curr, shift; \ + \ + a2[0] = array; \ + a2[1] = temp? temp : (type_t*)malloc(sizeof(type_t) * n); \ + for (curr = 0, shift = 0; (1ul<> 1) - 1; i != (size_t)(-1); --i) \ + ks_heapadjust_##name(i, lsize, l); \ + } \ + void ks_heapsort_##name(size_t lsize, type_t l[]) \ + { \ + size_t i; \ + for (i = lsize - 1; i > 0; --i) { \ + type_t tmp; \ + tmp = *l; *l = l[i]; l[i] = tmp; ks_heapadjust_##name(0, i, l); \ + } \ + } \ + inline void __ks_insertsort_##name(type_t *s, type_t *t) \ + { \ + type_t *i, *j, swap_tmp; \ + for (i = s + 1; i < t; ++i) \ + for (j = i; j > s && __sort_lt(*j, *(j-1)); --j) { \ + swap_tmp = *j; *j = *(j-1); *(j-1) = swap_tmp; \ + } \ + } \ + void ks_combsort_##name(size_t n, type_t a[]) \ + { \ + const double shrink_factor = 1.2473309501039786540366528676643; \ + int do_swap; \ + size_t gap = n; \ + type_t tmp, *i, *j; \ + do { \ + if (gap > 2) { \ + gap = (size_t)(gap / shrink_factor); \ + if (gap == 9 || gap == 10) gap = 11; \ + } \ + do_swap = 0; \ + for (i = a; i < a + n - gap; ++i) { \ + j = i + gap; \ + if (__sort_lt(*j, *i)) { \ + tmp = *i; *i = *j; *j = tmp; \ + do_swap = 1; \ + } \ + } \ + } while (do_swap || gap > 2); \ + if (gap != 1) __ks_insertsort_##name(a, a + n); \ + } \ + void ks_introsort_##name(size_t n, type_t a[]) \ + { \ + int d; \ + ks_isort_stack_t *top, *stack; \ + type_t rp, swap_tmp; \ + type_t *s, *t, *i, *j, *k; \ + \ + if (n < 1) return; \ + else if (n == 2) { \ + if (__sort_lt(a[1], a[0])) { swap_tmp = a[0]; a[0] = a[1]; a[1] = swap_tmp; } \ + return; \ + } \ + for (d = 2; 1ul<>1) + 1; \ + if (__sort_lt(*k, *i)) { \ + if (__sort_lt(*k, *j)) k = j; \ + } else k = __sort_lt(*j, *i)? i : j; \ + rp = *k; \ + if (k != t) { swap_tmp = *k; *k = *t; *t = swap_tmp; } \ + for (;;) { \ + do ++i; while (__sort_lt(*i, rp)); \ + do --j; while (i <= j && __sort_lt(rp, *j)); \ + if (j <= i) break; \ + swap_tmp = *i; *i = *j; *j = swap_tmp; \ + } \ + swap_tmp = *i; *i = *t; *t = swap_tmp; \ + if (i-s > t-i) { \ + if (i-s > 16) { top->left = s; top->right = i-1; top->depth = d; ++top; } \ + s = t-i > 16? i+1 : t; \ + } else { \ + if (t-i > 16) { top->left = i+1; top->right = t; top->depth = d; ++top; } \ + t = i-s > 16? i-1 : s; \ + } \ + } else { \ + if (top == stack) { \ + free(stack); \ + __ks_insertsort_##name(a, a+n); \ + return; \ + } else { --top; s = (type_t*)top->left; t = (type_t*)top->right; d = top->depth; } \ + } \ + } \ + } \ + /* This function is adapted from: http://ndevilla.free.fr/median/ */ \ + /* 0 <= kk < n */ \ + type_t ks_ksmall_##name(size_t n, type_t arr[], size_t kk) \ + { \ + type_t *low, *high, *k, *ll, *hh, *mid; \ + low = arr; high = arr + n - 1; k = arr + kk; \ + for (;;) { \ + if (high <= low) return *k; \ + if (high == low + 1) { \ + if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ + return *k; \ + } \ + mid = low + (high - low) / 2; \ + if (__sort_lt(*high, *mid)) KSORT_SWAP(type_t, *mid, *high); \ + if (__sort_lt(*high, *low)) KSORT_SWAP(type_t, *low, *high); \ + if (__sort_lt(*low, *mid)) KSORT_SWAP(type_t, *mid, *low); \ + KSORT_SWAP(type_t, *mid, *(low+1)); \ + ll = low + 1; hh = high; \ + for (;;) { \ + do ++ll; while (__sort_lt(*ll, *low)); \ + do --hh; while (__sort_lt(*low, *hh)); \ + if (hh < ll) break; \ + KSORT_SWAP(type_t, *ll, *hh); \ + } \ + KSORT_SWAP(type_t, *low, *hh); \ + if (hh <= k) low = ll; \ + if (hh >= k) high = hh - 1; \ + } \ + } + +#define ks_mergesort(name, n, a, t) ks_mergesort_##name(n, a, t) +#define ks_introsort(name, n, a) ks_introsort_##name(n, a) +#define ks_combsort(name, n, a) ks_combsort_##name(n, a) +#define ks_heapsort(name, n, a) ks_heapsort_##name(n, a) +#define ks_heapmake(name, n, a) ks_heapmake_##name(n, a) +#define ks_heapadjust(name, i, n, a) ks_heapadjust_##name(i, n, a) +#define ks_ksmall(name, n, a, k) ks_ksmall_##name(n, a, k) + +#define ks_lt_generic(a, b) ((a) < (b)) +#define ks_lt_str(a, b) (strcmp((a), (b)) < 0) + +typedef const char *ksstr_t; + +#define KSORT_INIT_GENERIC(type_t) KSORT_INIT(type_t, type_t, ks_lt_generic) +#define KSORT_INIT_STR KSORT_INIT(str, ksstr_t, ks_lt_str) + +#endif diff --git a/ksort_test.c b/ksort_test.c new file mode 100644 index 0000000..4a4e9d0 --- /dev/null +++ b/ksort_test.c @@ -0,0 +1,84 @@ +#include +#include +#include +#include +#include "ksort.h" + +KSORT_INIT_GENERIC(int) + +int main(int argc, char *argv[]) +{ + int i, N = 10000000; + int *array, x; + clock_t t1, t2; + if (argc > 1) N = atoi(argv[1]); + array = (int*)malloc(sizeof(int) * N); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + x = ks_ksmall(int, N, array, 10500); + t2 = clock(); + fprintf(stderr, "ksmall [%d]: %.3lf\n", x, (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort [%d]: %.3lf\n", array[10500], (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in introsort!\n"); + exit(1); + } + } + + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_combsort(int, N, array); + t2 = clock(); + fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in combsort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in mergesort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heapsort!\n"); + exit(1); + } + } + + free(array); + return 0; +} diff --git a/ksort_test.cc b/ksort_test.cc new file mode 100644 index 0000000..2cf8b8a --- /dev/null +++ b/ksort_test.cc @@ -0,0 +1,751 @@ +#include +#include +#include +#include +#include + +#include "ksort.h" +KSORT_INIT_GENERIC(int) + +using namespace std; + +/********************************** + * BEGIN OF PAUL'S IMPLEMENTATION * + **********************************/ + +/* Attractive Chaos: I have added inline where necessary. */ + +/* +Copyright (c) 2004 Paul Hsieh +All rights reserved. + +Redistribution and use in source and binary forms, with or without +modification, are permitted provided that the following conditions are met: + + Redistributions of source code must retain the above copyright notice, + this list of conditions and the following disclaimer. + + Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + Neither the name of sorttest nor the names of its contributors may be + used to endorse or promote products derived from this software without + specific prior written permission. + +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" +AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF +SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS +INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN +CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) +ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE +POSSIBILITY OF SUCH DAMAGE. +*/ + +/* + +Recommended flags: +------------------ + +Intel C/C++: +icl /O2 /G6 /Qaxi /Qxi /Qip sorttest.c + +WATCOM C/C++: +wcl386 /otexan /6r sorttest.c + +GCC: +gcc -O3 -mcpu=athlon-xp -march=athlon-xp sorttest.c + +MSVC: +cl /O2 /Ot /Og /G6 sorttest.c + +*/ + +static inline void sort2 (int * numbers) { +int tmp; + + if (numbers[0] <= numbers[1]) return; + tmp = numbers[0]; + numbers[0] = numbers[1]; + numbers[1] = tmp; +} + +static inline void sort3 (int * numbers) { +int tmp; + + if (numbers[0] <= numbers[1]) { + if (numbers[1] <= numbers[2]) return; + if (numbers[2] <= numbers[0]) { + tmp = numbers[0]; + numbers[0] = numbers[2]; + numbers[2] = numbers[1]; + numbers[1] = tmp; + return; + } + tmp = numbers[1]; + } else { + tmp = numbers[0]; + if (numbers[0] <= numbers[2]) { + numbers[0] = numbers[1]; + numbers[1] = tmp; + return; + } + if (numbers[2] <= numbers[1]) { + numbers[0] = numbers[2]; + numbers[2] = tmp; + return; + } + numbers[0] = numbers[1]; + } + numbers[1] = numbers[2]; + numbers[2] = tmp; +} + +static inline void sort4 (int * num) { +int tmp; + if (num[0] < num[1]) { + if (num[1] < num[2]) { + if (num[1] < num[3]) { + if (num[2] >= num[3]) { + tmp = num[2]; + num[2] = num[3]; + num[3] = tmp; + } + } else { + tmp = num[1]; + if (num[0] < num[3]) { + num[1] = num[3]; + } else { + num[1] = num[0]; + num[0] = num[3]; + } + num[3] = num[2]; + num[2] = tmp; + } + } else { + if (num[0] < num[2]) { + if (num[2] < num[3]) { + if (num[1] < num[3]) { + tmp = num[1]; + } else { + tmp = num[3]; + num[3] = num[1]; + } + num[1] = num[2]; + num[2] = tmp; + } else { + if (num[0] < num[3]) { + tmp = num[3]; + } else { + tmp = num[0]; + num[0] = num[3]; + } + num[3] = num[1]; + num[1] = tmp; + } + } else { + if (num[0] < num[3]) { + tmp = num[0]; + num[0] = num[2]; + if (num[1] < num[3]) { + num[2] = num[1]; + } else { + num[2] = num[3]; + num[3] = num[1]; + } + num[1] = tmp; + } else { + if (num[2] < num[3]) { + tmp = num[0]; + num[0] = num[2]; + num[2] = tmp; + tmp = num[1]; + num[1] = num[3]; + } else { + tmp = num[1]; + num[1] = num[2]; + num[2] = num[0]; + num[0] = num[3]; + } + num[3] = tmp; + } + } + } + } else { + tmp = num[0]; + if (tmp < num[2]) { + if (tmp < num[3]) { + num[0] = num[1]; + num[1] = tmp; + if (num[2] >= num[3]) { + tmp = num[2]; + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[1]; + num[1] = num[3]; + } else { + num[0] = num[3]; + } + num[3] = num[2]; + num[2] = tmp; + } + } else { + if (num[1] < num[2]) { + if (num[2] < num[3]) { + num[0] = num[1]; + num[1] = num[2]; + if (tmp < num[3]) { + num[2] = tmp; + } else { + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[1]; + num[1] = num[3]; + } else { + num[0] = num[3]; + } + num[3] = tmp; + } + } else { + if (num[1] < num[3]) { + num[0] = num[2]; + if (tmp < num[3]) { + num[2] = tmp; + } else { + num[2] = num[3]; + num[3] = tmp; + } + } else { + if (num[2] < num[3]) { + num[0] = num[2]; + num[2] = num[1]; + num[1] = num[3]; + num[3] = tmp; + } else { + num[0] = num[3]; + num[3] = tmp; + tmp = num[1]; + num[1] = num[2]; + num[2] = tmp; + } + } + } + } + } +} + +static inline void sortAlt2 (int * numbers, int * altNumbers) { + if (numbers[0] <= numbers[1]) { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[1]; + } else { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[0]; + } +} + +static inline void sortAlt3 (int * numbers, int * altNumbers) { + if (numbers[0] <= numbers[1]) { + if (numbers[1] <= numbers[2]) { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[1]; + altNumbers[2] = numbers[2]; + } else if (numbers[2] <= numbers[0]) { + altNumbers[0] = numbers[2]; + altNumbers[1] = numbers[0]; + altNumbers[2] = numbers[1]; + } else { + altNumbers[0] = numbers[0]; + altNumbers[1] = numbers[2]; + altNumbers[2] = numbers[1]; + } + } else { + if (numbers[0] <= numbers[2]) { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[0]; + altNumbers[2] = numbers[2]; + } else if (numbers[2] <= numbers[1]) { + altNumbers[0] = numbers[2]; + altNumbers[1] = numbers[1]; + altNumbers[2] = numbers[0]; + } else { + altNumbers[0] = numbers[1]; + altNumbers[1] = numbers[2]; + altNumbers[2] = numbers[0]; + } + } +} + +/* + * Insert Sort + */ + +inline void insertSort (int numbers[], int qty) { +int i, j, idx, q4; +int tmp; + + if (qty <= 4) { + if (qty == 4) sort4 (numbers); + else if (qty == 3) sort3 (numbers); + else if (qty == 2) sort2 (numbers); + return; + } + + q4 = qty - 4; + + for (i=0; i < q4; i++) { + idx = i; + for (j=i+1; j < qty; j++) { + if (numbers[j] < numbers[idx]) idx = j; + } + if (idx != i) { + tmp = numbers[idx]; + numbers[idx] = numbers[i]; + numbers[i] = tmp; + } + } + + sort4 (numbers + q4); +} + +/* + * Heap Sort + */ + +/* Assure the heap property for entries from top to last */ +static void siftDown (int numbers[], int top, int last) { +int tmp = numbers[top]; +int maxIdx = top; + + while (last >= (maxIdx += maxIdx)) { + + /* This is where the comparison occurrs and where a sufficiently + good compiler can use a computed conditional result rather + than using control logic. */ + if (maxIdx != last && numbers[maxIdx] < numbers[maxIdx + 1]) maxIdx++; + + if (tmp >= numbers[maxIdx]) break; + numbers[top] = numbers[maxIdx]; + top = maxIdx; + } + numbers[top] = tmp; +} + +/* Peel off the top siftDown operation since its parameters are trivial to + fill in directly (and this saves us some moves.) */ +static void siftDown0 (int numbers[], int last) { +int tmp; + + if (numbers[0] < numbers[1]) { + tmp = numbers[1]; + numbers[1] = numbers[0]; + siftDown (numbers, 1, last); + } else { + tmp = numbers[0]; + } + numbers[0] = numbers[last]; + numbers[last] = tmp; +} + +void heapSort (int numbers[], int qty) { +int i; + + if (qty <= 4) { + if (qty == 4) sort4 (numbers); + else if (qty == 3) sort3 (numbers); + else if (qty == 2) sort2 (numbers); + return; + } + + i = qty / 2; + /* Enforce the heap property for each position in the tree */ + for ( qty--; i > 0; i--) siftDown (numbers, i, qty); + for (i = qty; i > 0; i--) siftDown0 (numbers, i); +} + +/* + * Quick Sort + */ + +static int medianOf3 (int * numbers, int i, int j) { +int tmp; + + if (numbers[0] <= numbers[i]) { + if (numbers[j] <= numbers[0]) return numbers[0]; /* j 0 i */ + if (numbers[i] <= numbers[j]) j = i; /* 0 i j */ + /* 0 j i */ + } else { + if (numbers[0] <= numbers[j]) return numbers[0]; /* i 0 j */ + if (numbers[j] <= numbers[i]) j = i; /* j i 0 */ + /* i j 0 */ + } + tmp = numbers[j]; + numbers[j] = numbers[0]; + numbers[0] = tmp; + return tmp; +} + +static void quickSortRecurse (int * numbers, int left, int right) { +int pivot, lTmp, rTmp; + + qsrStart:; + +#if defined(__GNUC__) + if (right <= left + 8) { + insertSort (numbers + left, right - left + 1); + return; + } +#else + if (right <= left + 3) { + if (right == left + 1) { + sort2 (numbers + left); + } else if (right == left + 2) { + sort3 (numbers + left); + } else if (right == left + 3) { + sort4 (numbers + left); + } + return; + } +#endif + + lTmp = left; + rTmp = right; + + pivot = medianOf3 (numbers + left, (right-left) >> 1, right-1-left); + + goto QStart; + while (1) { + do { + right--; + if (left >= right) goto QEnd; + QStart:; + } while (numbers[right] > pivot); + numbers[left] = numbers[right]; + do { + left++; + if (left >= right) { + left = right; + goto QEnd; + } + } while (numbers[ left] < pivot); + numbers[right] = numbers[left]; + } + QEnd:; + numbers[left] = pivot; + + /* Only recurse the smaller partition */ + + if (left-1 - lTmp <= rTmp - left - 1) { + if (lTmp < left) quickSortRecurse (numbers, lTmp, left-1); + + /* Set up for larger partition */ + left++; + right = rTmp; + } else { + if (rTmp > left) quickSortRecurse (numbers, left+1, rTmp); + + /* Set up for larger partition */ + right = left - 1; + left = lTmp; + } + + /* Rerun with larger partition (recursion not required.) */ + goto qsrStart; +} + +void quickSort (int numbers[], int qty) { + if (qty < 2) return; + quickSortRecurse (numbers, 0, qty - 1); +} + +/* + * Merge Sort + */ + +static void mergesortInPlace (int * numbers, int * altNumbers, int qty); + +/* Perform mergesort, but store results in altNumbers */ + +static void mergesortExchange (int * numbers, int * altNumbers, int qty) { +int half, i0, i1, i; + + if (qty == 2) { + sortAlt2 (numbers, altNumbers); + return; + } + if (qty == 3) { + sortAlt3 (numbers, altNumbers); + return; + } + + half = (qty + 1)/2; + + mergesortInPlace (numbers, altNumbers, half); + mergesortInPlace (numbers + half, altNumbers, qty - half); + + i0 = 0; i1 = half; + + for (i=0; i < qty; i++) { + if (i1 >= qty || (i0 < half && numbers[i0] < numbers[i1])) { + altNumbers[i] = numbers[i0]; + i0++; + } else { + altNumbers[i] = numbers[i1]; + i1++; + } + } +} + +/* Perform mergesort and store results in numbers */ + +static void mergesortInPlace (int * numbers, int * altNumbers, int qty) { +int half, i0, i1, i; + +#if 0 + if (qty == 2) { + sort2 (numbers); + return; + } + if (qty == 3) { + sort3 (numbers); + return; + } + if (qty == 4) { + sort4 (numbers); + return; + } +#else + if (qty <= 12) { + insertSort (numbers, qty); + return; + } +#endif + + half = (qty + 1)/2; + + mergesortExchange (numbers, altNumbers, half); + mergesortExchange (numbers + half, altNumbers + half, qty - half); + + i0 = 0; i1 = half; + + for (i=0; i < qty; i++) { + if (i1 >= qty || (i0 < half && altNumbers[i0] < altNumbers[i1])) { + numbers[i] = altNumbers[i0]; + i0++; + } else { + numbers[i] = altNumbers[i1]; + i1++; + } + } +} + +#include + +void mergeSort (int numbers[], int qty) { +int * tmpArray; + + if (qty <= 12) { + insertSort (numbers, qty); + return; + } + + tmpArray = (int *) malloc (qty * sizeof (int)); + mergesortInPlace (numbers, tmpArray, qty); + free (tmpArray); +} + +/******************************** + * END OF PAUL'S IMPLEMENTATION * + ********************************/ + +struct intcmp_t { + inline int operator() (int a, int b) const { + return a < b? -1 : a > b? 1 : 0; + } +}; + +int compare_int(int a, int b) +{ + return a < b? -1 : a > b? 1 : 0; +} +int compare(const void *a, const void *b) +{ + return *((int*)a) - *((int*)b); +} + +int main(int argc, char *argv[]) +{ + int i, N = 50000000; + int *array, *temp; + clock_t t1, t2; + if (argc == 1) fprintf(stderr, "Usage: %s [%d]\n", argv[0], N); + if (argc > 1) N = atoi(argv[1]); + temp = (int*)malloc(sizeof(int) * N); + array = (int*)malloc(sizeof(int) * N); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + t1 = clock(); + sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + stable_sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL stablesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + t1 = clock(); + stable_sort(array, array+N); + t2 = clock(); + fprintf(stderr, "STL stablesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + make_heap(array, array+N); + sort_heap(array, array+N); + t2 = clock(); + fprintf(stderr, "STL heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heap_sort!\n"); + exit(1); + } + } + t1 = clock(); + make_heap(array, array+N); + sort_heap(array, array+N); + t2 = clock(); + fprintf(stderr, "STL heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_combsort(int, N, array); + t2 = clock(); + fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in combsort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + qsort(array, N, sizeof(int), compare); + t2 = clock(); + fprintf(stderr, "libc qsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "my introsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_introsort(int, N, array); + t2 = clock(); + fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "iterative mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in merge_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_mergesort(int, N, array, 0); + t2 = clock(); + fprintf(stderr, "iterative mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "my heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in heap_sort!\n"); + exit(1); + } + } + t1 = clock(); + ks_heapmake(int, N, array); + ks_heapsort(int, N, array); + t2 = clock(); + fprintf(stderr, "heapsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + heapSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + quickSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's quicksort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + srand48(11); + for (i = 0; i < N; ++i) array[i] = (int)lrand48(); + t1 = clock(); + mergeSort(array, N); + t2 = clock(); + fprintf(stderr, "Paul's mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); + for (i = 0; i < N-1; ++i) { + if (array[i] > array[i+1]) { + fprintf(stderr, "Bug in intro_sort!\n"); + exit(1); + } + } + + free(array); free(temp); + return 0; +} -- 2.47.3