From f4c20290509d7ed3a8fd5304577e7a4cc0b9d974 Mon Sep 17 00:00:00 2001 From: Mike Buland Date: Tue, 3 Apr 2007 03:49:53 +0000 Subject: Ok, no code is left in src, it's all in src/old. We'll gradually move code back into src as it's fixed and re-org'd. This includes tests, which, I may write a unit test system into libbu++ just to make my life easier. --- src/old/tqsort.h | 207 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 207 insertions(+) create mode 100644 src/old/tqsort.h (limited to 'src/old/tqsort.h') diff --git a/src/old/tqsort.h b/src/old/tqsort.h new file mode 100644 index 0000000..c836b4f --- /dev/null +++ b/src/old/tqsort.h @@ -0,0 +1,207 @@ +#ifndef T_QSORT_H +#define T_QSORT_H + +#define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t))) + +/* Discontinue quicksort algorithm when partition gets below this size. + This particular magic number was chosen to work best on a Sun 4/260. */ +#define _QSORT_MAX_THRESH 4 + +/* Stack node declarations used to store unfulfilled partition obligations + * (inlined in QSORT). +typedef struct { + QSORT_TYPE *_lo, *_hi; +} qsort_stack_node; + */ + +/* The next 4 #defines implement a very fast in-line stack abstraction. */ +/* The stack needs log (total_elements) entries (we could even subtract + log(MAX_THRESH)). Since total_elements has type unsigned, we get as + upper bound for log (total_elements): + bits per byte (CHAR_BIT) * sizeof(unsigned). */ +#define _QSORT_STACK_SIZE (8 * sizeof(unsigned)) +#define _QSORT_PUSH(top, low, high) \ + (((top->_lo = (low)), (top->_hi = (high)), ++top)) +#define _QSORT_POP(low, high, top) \ + ((--top, (low = top->_lo), (high = top->_hi))) +#define _QSORT_STACK_NOT_EMPTY (_stack < _top) + + +/* Order size using quicksort. This implementation incorporates + four optimizations discussed in Sedgewick: + + 1. Non-recursive, using an explicit stack of pointer that store the + next array partition to sort. To save time, this maximum amount + of space required to store an array of SIZE_MAX is allocated on the + stack. Assuming a 32-bit (64 bit) integer for size_t, this needs + only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes). + Pretty cheap, actually. + + 2. Chose the pivot element using a median-of-three decision tree. + This reduces the probability of selecting a bad pivot value and + eliminates certain extraneous comparisons. + + 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving + insertion sort to order the MAX_THRESH items within each partition. + This is a big win, since insertion sort is faster for small, mostly + sorted array segments. + + 4. The larger of the two sub-partitions is always pushed onto the + stack first, with the algorithm then concentrating on the + smaller partition. This *guarantees* no more than log (total_elems) + stack size is needed (actually O(1) in this case)! */ + +/* The main code starts here... */ + +template +void tqsort( QSORT_TYPE *QSORT_BASE, int QSORT_NELT ) +{ + QSORT_LTT QSORT_LT; + QSORT_TYPE *const _base = (QSORT_BASE); + const unsigned _elems = (QSORT_NELT); + QSORT_TYPE _hold; + + /* Don't declare two variables of type QSORT_TYPE in a single + * statement: eg `TYPE a, b;', in case if TYPE is a pointer, + * expands to `type* a, b;' wich isn't what we want. + */ + + if (_elems > _QSORT_MAX_THRESH) { + QSORT_TYPE *_lo = _base; + QSORT_TYPE *_hi = _lo + _elems - 1; + struct { + QSORT_TYPE *_hi; QSORT_TYPE *_lo; + } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1; + + while (_QSORT_STACK_NOT_EMPTY) { + QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr; + + /* Select median value from among LO, MID, and HI. Rearrange + LO and HI so the three values are sorted. This lowers the + probability of picking a pathological pivot value and + skips a comparison for both the LEFT_PTR and RIGHT_PTR in + the while loops. */ + + QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1); + + if (QSORT_LT ((CST)(_mid), (CST)(_lo))) + _QSORT_SWAP (_mid, _lo, _hold); + if (QSORT_LT ((CST)(_hi), (CST)(_mid))) + _QSORT_SWAP (_mid, _hi, _hold); + else + goto _jump_over; + if (QSORT_LT ((CST)(_mid), (CST)(_lo))) + _QSORT_SWAP (_mid, _lo, _hold); + _jump_over:; + + _left_ptr = _lo + 1; + _right_ptr = _hi - 1; + + /* Here's the famous ``collapse the walls'' section of quicksort. + Gotta like those tight inner loops! They are the main reason + that this algorithm runs much faster than others. */ + do { + while (QSORT_LT ((CST)(_left_ptr), (CST)(_mid))) + ++_left_ptr; + + while (QSORT_LT ((CST)(_mid), (CST)(_right_ptr))) + --_right_ptr; + + if (_left_ptr < _right_ptr) { + _QSORT_SWAP (_left_ptr, _right_ptr, _hold); + if (_mid == _left_ptr) + _mid = _right_ptr; + else if (_mid == _right_ptr) + _mid = _left_ptr; + ++_left_ptr; + --_right_ptr; + } + else if (_left_ptr == _right_ptr) { + ++_left_ptr; + --_right_ptr; + break; + } + } while (_left_ptr <= _right_ptr); + + /* Set up pointers for next iteration. First determine whether + left and right partitions are below the threshold size. If so, + ignore one or both. Otherwise, push the larger partition's + bounds on the stack and continue sorting the smaller one. */ + + if (_right_ptr - _lo <= _QSORT_MAX_THRESH) { + if (_hi - _left_ptr <= _QSORT_MAX_THRESH) + /* Ignore both small partitions. */ + _QSORT_POP (_lo, _hi, _top); + else + /* Ignore small left partition. */ + _lo = _left_ptr; + } + else if (_hi - _left_ptr <= _QSORT_MAX_THRESH) + /* Ignore small right partition. */ + _hi = _right_ptr; + else if (_right_ptr - _lo > _hi - _left_ptr) { + /* Push larger left partition indices. */ + _QSORT_PUSH (_top, _lo, _right_ptr); + _lo = _left_ptr; + } + else { + /* Push larger right partition indices. */ + _QSORT_PUSH (_top, _left_ptr, _hi); + _hi = _right_ptr; + } + } + } + + /* Once the BASE array is partially sorted by quicksort the rest + is completely sorted using insertion sort, since this is efficient + for partitions below MAX_THRESH size. BASE points to the + beginning of the array to sort, and END_PTR points at the very + last element in the array (*not* one beyond it!). */ + + { + QSORT_TYPE *const _end_ptr = _base + _elems - 1; + QSORT_TYPE *_tmp_ptr = _base; + register QSORT_TYPE *_run_ptr; + QSORT_TYPE *_thresh; + + _thresh = _base + _QSORT_MAX_THRESH; + if (_thresh > _end_ptr) + _thresh = _end_ptr; + + /* Find smallest element in first threshold and place it at the + array's beginning. This is the smallest array element, + and the operation speeds up insertion sort's inner loop. */ + + for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr) + if (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr))) + _tmp_ptr = _run_ptr; + + if (_tmp_ptr != _base) + _QSORT_SWAP (_tmp_ptr, _base, _hold); + + /* Insertion sort, running from left-hand-side + * up to right-hand-side. */ + + _run_ptr = _base + 1; + while (++_run_ptr <= _end_ptr) { + _tmp_ptr = _run_ptr - 1; + while (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr))) + --_tmp_ptr; + + ++_tmp_ptr; + if (_tmp_ptr != _run_ptr) { + QSORT_TYPE *_trav = _run_ptr + 1; + while (--_trav >= _run_ptr) { + QSORT_TYPE *_hi; QSORT_TYPE *_lo; + _hold = *_trav; + + for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo) + *_hi = *_lo; + *_hi = _hold; + } + } + } + } +} + +#endif -- cgit v1.2.3