summaryrefslogtreecommitdiff
path: root/src/tqsort.h
diff options
context:
space:
mode:
authorMike Buland <eichlan@xagasoft.com>2007-04-03 03:49:53 +0000
committerMike Buland <eichlan@xagasoft.com>2007-04-03 03:49:53 +0000
commitf4c20290509d7ed3a8fd5304577e7a4cc0b9d974 (patch)
tree13cdf64f7cf134f397a7165b7a3fe0807e37026b /src/tqsort.h
parent74d4c8cd27334fc7204d5a8773deb3d424565778 (diff)
downloadlibbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.gz
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.bz2
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.tar.xz
libbu++-f4c20290509d7ed3a8fd5304577e7a4cc0b9d974.zip
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.
Diffstat (limited to 'src/tqsort.h')
-rw-r--r--src/tqsort.h207
1 files changed, 0 insertions, 207 deletions
diff --git a/src/tqsort.h b/src/tqsort.h
deleted file mode 100644
index c836b4f..0000000
--- a/src/tqsort.h
+++ /dev/null
@@ -1,207 +0,0 @@
1#ifndef T_QSORT_H
2#define T_QSORT_H
3
4#define _QSORT_SWAP(a, b, t) ((void)((t = *a), (*a = *b), (*b = t)))
5
6/* Discontinue quicksort algorithm when partition gets below this size.
7 This particular magic number was chosen to work best on a Sun 4/260. */
8#define _QSORT_MAX_THRESH 4
9
10/* Stack node declarations used to store unfulfilled partition obligations
11 * (inlined in QSORT).
12typedef struct {
13 QSORT_TYPE *_lo, *_hi;
14} qsort_stack_node;
15 */
16
17/* The next 4 #defines implement a very fast in-line stack abstraction. */
18/* The stack needs log (total_elements) entries (we could even subtract
19 log(MAX_THRESH)). Since total_elements has type unsigned, we get as
20 upper bound for log (total_elements):
21 bits per byte (CHAR_BIT) * sizeof(unsigned). */
22#define _QSORT_STACK_SIZE (8 * sizeof(unsigned))
23#define _QSORT_PUSH(top, low, high) \
24 (((top->_lo = (low)), (top->_hi = (high)), ++top))
25#define _QSORT_POP(low, high, top) \
26 ((--top, (low = top->_lo), (high = top->_hi)))
27#define _QSORT_STACK_NOT_EMPTY (_stack < _top)
28
29
30/* Order size using quicksort. This implementation incorporates
31 four optimizations discussed in Sedgewick:
32
33 1. Non-recursive, using an explicit stack of pointer that store the
34 next array partition to sort. To save time, this maximum amount
35 of space required to store an array of SIZE_MAX is allocated on the
36 stack. Assuming a 32-bit (64 bit) integer for size_t, this needs
37 only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
38 Pretty cheap, actually.
39
40 2. Chose the pivot element using a median-of-three decision tree.
41 This reduces the probability of selecting a bad pivot value and
42 eliminates certain extraneous comparisons.
43
44 3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
45 insertion sort to order the MAX_THRESH items within each partition.
46 This is a big win, since insertion sort is faster for small, mostly
47 sorted array segments.
48
49 4. The larger of the two sub-partitions is always pushed onto the
50 stack first, with the algorithm then concentrating on the
51 smaller partition. This *guarantees* no more than log (total_elems)
52 stack size is needed (actually O(1) in this case)! */
53
54/* The main code starts here... */
55
56template<typename QSORT_TYPE, typename QSORT_LTT, typename CST>
57void tqsort( QSORT_TYPE *QSORT_BASE, int QSORT_NELT )
58{
59 QSORT_LTT QSORT_LT;
60 QSORT_TYPE *const _base = (QSORT_BASE);
61 const unsigned _elems = (QSORT_NELT);
62 QSORT_TYPE _hold;
63
64 /* Don't declare two variables of type QSORT_TYPE in a single
65 * statement: eg `TYPE a, b;', in case if TYPE is a pointer,
66 * expands to `type* a, b;' wich isn't what we want.
67 */
68
69 if (_elems > _QSORT_MAX_THRESH) {
70 QSORT_TYPE *_lo = _base;
71 QSORT_TYPE *_hi = _lo + _elems - 1;
72 struct {
73 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
74 } _stack[_QSORT_STACK_SIZE], *_top = _stack + 1;
75
76 while (_QSORT_STACK_NOT_EMPTY) {
77 QSORT_TYPE *_left_ptr; QSORT_TYPE *_right_ptr;
78
79 /* Select median value from among LO, MID, and HI. Rearrange
80 LO and HI so the three values are sorted. This lowers the
81 probability of picking a pathological pivot value and
82 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
83 the while loops. */
84
85 QSORT_TYPE *_mid = _lo + ((_hi - _lo) >> 1);
86
87 if (QSORT_LT ((CST)(_mid), (CST)(_lo)))
88 _QSORT_SWAP (_mid, _lo, _hold);
89 if (QSORT_LT ((CST)(_hi), (CST)(_mid)))
90 _QSORT_SWAP (_mid, _hi, _hold);
91 else
92 goto _jump_over;
93 if (QSORT_LT ((CST)(_mid), (CST)(_lo)))
94 _QSORT_SWAP (_mid, _lo, _hold);
95 _jump_over:;
96
97 _left_ptr = _lo + 1;
98 _right_ptr = _hi - 1;
99
100 /* Here's the famous ``collapse the walls'' section of quicksort.
101 Gotta like those tight inner loops! They are the main reason
102 that this algorithm runs much faster than others. */
103 do {
104 while (QSORT_LT ((CST)(_left_ptr), (CST)(_mid)))
105 ++_left_ptr;
106
107 while (QSORT_LT ((CST)(_mid), (CST)(_right_ptr)))
108 --_right_ptr;
109
110 if (_left_ptr < _right_ptr) {
111 _QSORT_SWAP (_left_ptr, _right_ptr, _hold);
112 if (_mid == _left_ptr)
113 _mid = _right_ptr;
114 else if (_mid == _right_ptr)
115 _mid = _left_ptr;
116 ++_left_ptr;
117 --_right_ptr;
118 }
119 else if (_left_ptr == _right_ptr) {
120 ++_left_ptr;
121 --_right_ptr;
122 break;
123 }
124 } while (_left_ptr <= _right_ptr);
125
126 /* Set up pointers for next iteration. First determine whether
127 left and right partitions are below the threshold size. If so,
128 ignore one or both. Otherwise, push the larger partition's
129 bounds on the stack and continue sorting the smaller one. */
130
131 if (_right_ptr - _lo <= _QSORT_MAX_THRESH) {
132 if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
133 /* Ignore both small partitions. */
134 _QSORT_POP (_lo, _hi, _top);
135 else
136 /* Ignore small left partition. */
137 _lo = _left_ptr;
138 }
139 else if (_hi - _left_ptr <= _QSORT_MAX_THRESH)
140 /* Ignore small right partition. */
141 _hi = _right_ptr;
142 else if (_right_ptr - _lo > _hi - _left_ptr) {
143 /* Push larger left partition indices. */
144 _QSORT_PUSH (_top, _lo, _right_ptr);
145 _lo = _left_ptr;
146 }
147 else {
148 /* Push larger right partition indices. */
149 _QSORT_PUSH (_top, _left_ptr, _hi);
150 _hi = _right_ptr;
151 }
152 }
153 }
154
155 /* Once the BASE array is partially sorted by quicksort the rest
156 is completely sorted using insertion sort, since this is efficient
157 for partitions below MAX_THRESH size. BASE points to the
158 beginning of the array to sort, and END_PTR points at the very
159 last element in the array (*not* one beyond it!). */
160
161 {
162 QSORT_TYPE *const _end_ptr = _base + _elems - 1;
163 QSORT_TYPE *_tmp_ptr = _base;
164 register QSORT_TYPE *_run_ptr;
165 QSORT_TYPE *_thresh;
166
167 _thresh = _base + _QSORT_MAX_THRESH;
168 if (_thresh > _end_ptr)
169 _thresh = _end_ptr;
170
171 /* Find smallest element in first threshold and place it at the
172 array's beginning. This is the smallest array element,
173 and the operation speeds up insertion sort's inner loop. */
174
175 for (_run_ptr = _tmp_ptr + 1; _run_ptr <= _thresh; ++_run_ptr)
176 if (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr)))
177 _tmp_ptr = _run_ptr;
178
179 if (_tmp_ptr != _base)
180 _QSORT_SWAP (_tmp_ptr, _base, _hold);
181
182 /* Insertion sort, running from left-hand-side
183 * up to right-hand-side. */
184
185 _run_ptr = _base + 1;
186 while (++_run_ptr <= _end_ptr) {
187 _tmp_ptr = _run_ptr - 1;
188 while (QSORT_LT ((CST)(_run_ptr), (CST)(_tmp_ptr)))
189 --_tmp_ptr;
190
191 ++_tmp_ptr;
192 if (_tmp_ptr != _run_ptr) {
193 QSORT_TYPE *_trav = _run_ptr + 1;
194 while (--_trav >= _run_ptr) {
195 QSORT_TYPE *_hi; QSORT_TYPE *_lo;
196 _hold = *_trav;
197
198 for (_hi = _lo = _trav; --_lo >= _tmp_ptr; _hi = _lo)
199 *_hi = *_lo;
200 *_hi = _hold;
201 }
202 }
203 }
204 }
205}
206
207#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-29 14:41:23 +0000