1 // See LICENSE for license details.
3 //**************************************************************************
5 //--------------------------------------------------------------------------
7 // This benchmark uses quicksort to sort an array of integers. The
8 // implementation is largely adapted from Numerical Recipes for C. The
9 // input data (and reference data) should be generated using the
10 // qsort_gendata.pl perl script and dumped to a file named
17 // The INSERTION_THRESHOLD is the size of the subarray when the
18 // algorithm switches to using an insertion sort instead of
21 #define INSERTION_THRESHOLD 10
23 // NSTACK is the required auxiliary storage.
24 // It must be at least 2*lg(DATA_SIZE)
28 //--------------------------------------------------------------------------
29 // Input/Reference Data
34 // Swap macro for swapping two values.
36 #define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
37 #define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
39 //--------------------------------------------------------------------------
42 static void insertion_sort(size_t n
, type arr
[])
46 for (i
= arr
+1; i
< arr
+n
; i
++)
50 while (value
< *(j
-1))
60 static void selection_sort(size_t n
, type arr
[])
62 for (type
* i
= arr
; i
< arr
+n
-1; i
++)
63 for (type
* j
= i
+1; j
< arr
+n
; j
++)
64 SWAP_IF_GREATER(*i
, *j
);
67 void sort(size_t n
, type arr
[])
72 type
** stackp
= stack
;
76 // Insertion sort when subarray small enough.
77 if ( ir
-l
< INSERTION_THRESHOLD
)
79 insertion_sort(ir
- l
+ 1, l
- 1);
81 if ( stackp
== stack
) break;
83 // Pop stack and begin a new round of partitioning.
89 // Choose median of left, center, and right elements as
90 // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
91 SWAP(arr
[((l
-arr
) + (ir
-arr
))/2-1], l
[0]);
92 SWAP_IF_GREATER(l
[-1], ir
[-1]);
93 SWAP_IF_GREATER(l
[0], ir
[-1]);
94 SWAP_IF_GREATER(l
[-1], l
[0]);
96 // Initialize pointers for partitioning.
100 // Partitioning element.
103 for (;;) { // Beginning of innermost loop.
104 while (*i
++ < a
); // Scan up to find element > a.
105 while (*(j
-- - 2) > a
); // Scan down to find element < a.
106 if (j
< i
) break; // Pointers crossed. Partitioning complete.
107 SWAP(i
[-1], j
[-1]); // Exchange elements.
108 } // End of innermost loop.
110 // Insert partitioning element.
115 // Push pointers to larger subarray on stack,
116 // process smaller subarray immediately.
134 //--------------------------------------------------------------------------
137 int main( int argc
, char* argv
[] )
140 // If needed we preallocate everything in the caches
141 sort(DATA_SIZE
, verify_data
);
142 if (verify(DATA_SIZE
, input_data
, input_data
))
148 sort( DATA_SIZE
, input_data
);
152 return verify( DATA_SIZE
, input_data
, verify_data
);