diff options
Diffstat (limited to '')
-rw-r--r-- | debian/vendor-h2o/deps/klib/test/ksort_test.cc | 997 |
1 files changed, 0 insertions, 997 deletions
diff --git a/debian/vendor-h2o/deps/klib/test/ksort_test.cc b/debian/vendor-h2o/deps/klib/test/ksort_test.cc deleted file mode 100644 index 8950d80..0000000 --- a/debian/vendor-h2o/deps/klib/test/ksort_test.cc +++ /dev/null @@ -1,997 +0,0 @@ -#include <stdlib.h> -#include <string.h> -#include <stdio.h> -#include <time.h> -#include <algorithm> - -#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 <stdlib.h> - -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 * - ********************************/ - -/************************************************* - *** Implementation 1: faster on sorted arrays *** - *************************************************/ - -#define rstype_t unsigned -#define rskey(x) (x) - -#define RS_MIN_SIZE 64 - -typedef struct { - rstype_t *b, *e; -} rsbucket_t; - -void rs_sort(rstype_t *beg, rstype_t *end, int n_bits, int s) -{ - rstype_t *i; - int size = 1<<n_bits, m = size - 1; - rsbucket_t *k, b[size], *be = b + size; - - for (k = b; k != be; ++k) k->b = k->e = beg; - for (i = beg; i != end; ++i) ++b[rskey(*i)>>s&m].e; - for (k = b + 1; k != be; ++k) - k->e += (k-1)->e - beg, k->b = (k-1)->e; - for (k = b; k != be;) { - if (k->b != k->e) { - rsbucket_t *l; - if ((l = b + (rskey(*k->b)>>s&m)) != k) { - rstype_t tmp = *k->b, swap; - do { - swap = tmp; tmp = *l->b; *l->b++ = swap; - l = b + (rskey(tmp)>>s&m); - } while (l != k); - *k->b++ = tmp; - } else ++k->b; - } else ++k; - } - for (b->b = beg, k = b + 1; k != be; ++k) k->b = (k-1)->e; - if (s) { - s = s > n_bits? s - n_bits : 0; - for (k = b; k != be; ++k) - if (k->e - k->b > RS_MIN_SIZE) rs_sort(k->b, k->e, n_bits, s); - else if (k->e - k->b > 1) - for (i = k->b + 1; i < k->e; ++i) - if (rskey(*i) < rskey(*(i - 1))) { - rstype_t *j, tmp = *i; - for (j = i; j > k->b && rskey(tmp) < rskey(*(j-1)); --j) - *j = *(j - 1); - *j = tmp; - } - } -} - -/************************************************* - *** Implementation 2: faster on random arrays *** - *************************************************/ - -static inline void rs_insertsort(rstype_t *s, rstype_t *t) -{ - rstype_t *i; - for (i = s + 1; i < t; ++i) { - if (rskey(*i) < rskey(*(i - 1))) { - rstype_t *j, tmp = *i; - for (j = i; j > s && rskey(tmp) < rskey(*(j-1)); --j) - *j = *(j - 1); - *j = tmp; - } - } -} -/* -void rs_sort2(rstype_t *beg, rstype_t *end, int n_bits, int s) -{ - int j, size = 1<<n_bits, m = size - 1; - unsigned long c[size]; - rstype_t *i, *b[size], *e[size]; - - for (j = 0; j < size; ++j) c[j] = 0; - for (i = beg; i != end; ++i) ++c[rskey(*i)>>s&m]; - b[0] = e[0] = beg; - for (j = 1; j != size; ++j) b[j] = e[j] = b[j - 1] + c[j - 1]; - for (i = beg, j = 0; i != end;) { - rstype_t tmp = *i, swap; - int x; - for (;;) { - x = rskey(tmp)>>s&m; - if (e[x] == i) break; - swap = tmp; tmp = *e[x]; *e[x]++ = swap; - } - *i++ = tmp; - ++e[x]; - while (j != size && i >= b[j]) ++j; - while (j != size && e[j-1] == b[j]) ++j; - if (i < e[j-1]) i = e[j-1]; - } - if (s) { - s = s > n_bits? s - n_bits : 0; - for (j = 0; j < size; ++j) { - if (c[j] >= RS_MIN_SIZE) rs_sort2(b[j], e[j], n_bits, s); - else if (c[j] >= 2) rs_insertsort(b[j], e[j]); - } - } -} -*/ -void radix_sort(unsigned *array, int offset, int end, int shift) { - int x, y, value, temp; - int last[256] = { 0 }, pointer[256]; - - for (x=offset; x<end; ++x) { - ++last[(array[x] >> shift) & 0xFF]; - } - - last[0] += offset; - pointer[0] = offset; - for (x=1; x<256; ++x) { - pointer[x] = last[x-1]; - last[x] += last[x-1]; - } - - for (x=0; x<256; ++x) { - while (pointer[x] != last[x]) { - value = array[pointer[x]]; - y = (value >> shift) & 0xFF; - while (x != y) { - temp = array[pointer[y]]; - array[pointer[y]++] = value; - value = temp; - y = (value >> shift) & 0xFF; - } - array[pointer[x]++] = value; - } - } - - if (shift > 0) { - shift -= 8; - for (x=0; x<256; ++x) { - temp = x > 0 ? pointer[x] - pointer[x-1] : pointer[0] - offset; - if (temp > 64) { - radix_sort(array, pointer[x] - temp, pointer[x], shift); - } else if (temp > 1) rs_insertsort(array + pointer[x] - temp, array + pointer[x]); - } - } -} -/************************* - *** END OF RADIX SORT *** - *************************/ - -template< class _Type, unsigned long PowerOfTwoRadix, unsigned long Log2ofPowerOfTwoRadix, long Threshold > -inline void _RadixSort_Unsigned_PowerOf2Radix_1( _Type* a, long last, _Type bitMask, unsigned long shiftRightAmount ) -{ - const unsigned long numberOfBins = PowerOfTwoRadix; - unsigned long count[ numberOfBins ]; - for( unsigned long i = 0; i < numberOfBins; i++ ) - count[ i ] = 0; - for ( long _current = 0; _current <= last; _current++ ) // Scan the array and count the number of times each value appears - { - unsigned long digit = (unsigned long)(( a[ _current ] & bitMask ) >> shiftRightAmount ); // extract the digit we are sorting based on - count[ digit ]++; - } - long startOfBin[ numberOfBins ], endOfBin[ numberOfBins ], nextBin; - startOfBin[ 0 ] = endOfBin[ 0 ] = nextBin = 0; - for( unsigned long i = 1; i < numberOfBins; i++ ) - startOfBin[ i ] = endOfBin[ i ] = startOfBin[ i - 1 ] + count[ i - 1 ]; - for ( long _current = 0; _current <= last; ) - { - unsigned long digit; - _Type tmp = a[ _current ]; // get the compiler to recognize that a register can be used for the loop instead of a[_current] memory location - while ( true ) { - digit = (unsigned long)(( tmp & bitMask ) >> shiftRightAmount ); // extract the digit we are sorting based on - if ( endOfBin[ digit ] == _current ) - break; - _Type tmp2; - //_swap( tmp, a[ endOfBin[ digit ] ] ); - tmp2 = a[endOfBin[digit]]; a[endOfBin[digit]] = tmp; tmp = tmp2; - endOfBin[ digit ]++; - } - a[ _current ] = tmp; - endOfBin[ digit ]++; // leave the element at its location and grow the bin - _current++; // advance the current pointer to the next element - while( _current >= startOfBin[ nextBin ] && nextBin < numberOfBins ) - nextBin++; - while( endOfBin[ nextBin - 1 ] == startOfBin[ nextBin ] && nextBin < numberOfBins ) - nextBin++; - if ( _current < endOfBin[ nextBin - 1 ] ) - _current = endOfBin[ nextBin - 1 ]; - } - bitMask >>= Log2ofPowerOfTwoRadix; - if ( bitMask != 0 ) // end recursion when all the bits have been processes - { - if ( shiftRightAmount >= Log2ofPowerOfTwoRadix ) shiftRightAmount -= Log2ofPowerOfTwoRadix; - else shiftRightAmount = 0; - for( unsigned long i = 0; i < numberOfBins; i++ ) - { - long numberOfElements = endOfBin[ i ] - startOfBin[ i ]; - if ( numberOfElements >= Threshold ) // endOfBin actually points to one beyond the bin - _RadixSort_Unsigned_PowerOf2Radix_1< _Type, PowerOfTwoRadix, Log2ofPowerOfTwoRadix, Threshold >( &a[ startOfBin[ i ]], numberOfElements - 1, bitMask, shiftRightAmount ); - else if ( numberOfElements >= 2 ) - rs_insertsort(&a[ startOfBin[ i ]], &a[ endOfBin[ i ]]); - } - } -} -inline void RadixSortInPlace_HybridUnsigned_Radix256( unsigned* a, unsigned long a_size ) -{ - if ( a_size < 2 ) return; - unsigned long bitMask = 0xFF000000; // bitMask controls how many bits we process at a time - unsigned long shiftRightAmount = 24; - if ( a_size >= 32 ) - _RadixSort_Unsigned_PowerOf2Radix_1<unsigned, 256, 8, 32>(a, a_size - 1, bitMask, shiftRightAmount ); - else - rs_insertsort(a, a + a_size); -} - -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(); - rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24); - t2 = clock(); - fprintf(stderr, "radix sort: %.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 radix sort!\n"); - exit(1); - } - } - t1 = clock(); - rs_sort((unsigned*)array, (unsigned*)array + N, 8, 24); - t2 = clock(); - fprintf(stderr, "radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); - - srand48(11); - for (i = 0; i < N; ++i) array[i] = (int)lrand48(); - t1 = clock(); - RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N); -// radix_sort((unsigned*)array, 0, N, 24); - t2 = clock(); - fprintf(stderr, "vd's radix sort: %.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 radix sort!\n"); - exit(1); - } - } - t1 = clock(); - RadixSortInPlace_HybridUnsigned_Radix256((unsigned*)array, N); -// radix_sort((unsigned*)array, 0, N, 24); - t2 = clock(); - fprintf(stderr, "vd's radix sort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC); - - 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; -} |