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