1 //**************************************************************************
3 //--------------------------------------------------------------------------
5 // This benchmark uses quicksort to sort an array of integers. The
6 // implementation is largely adapted from Numerical Recipes for C. The
7 // input data (and reference data) should be generated using the
8 // qsort_gendata.pl perl script and dumped to a file named
9 // dataset1.h The smips-gcc toolchain does not support system calls
10 // so printf's can only be used on a host system, not on the smips
11 // processor simulator itself. You should not change anything except
12 // the HOST_DEBUG and PREALLOCATE macros for your timing run.
18 // The INSERTION_THRESHOLD is the size of the subarray when the
19 // algorithm switches to using an insertion sort instead of
22 #define INSERTION_THRESHOLD 10
24 // NSTACK is the required auxiliary storage.
25 // It must be at least 2*lg(DATA_SIZE)
29 //--------------------------------------------------------------------------
30 // Input/Reference Data
35 // Swap macro for swapping two values.
37 #define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
38 #define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
40 //--------------------------------------------------------------------------
43 static void insertion_sort(size_t n
, type arr
[])
47 for (i
= arr
+1; i
< arr
+n
; i
++)
51 while (value
< *(j
-1))
61 static void selection_sort(size_t n
, type arr
[])
63 for (type
* i
= arr
; i
< arr
+n
-1; i
++)
64 for (type
* j
= i
+1; j
< arr
+n
; j
++)
65 SWAP_IF_GREATER(*i
, *j
);
68 void sort(size_t n
, type arr
[])
73 type
** stackp
= stack
;
78 printArray( "", n
, arr
);
81 // Insertion sort when subarray small enough.
82 if ( ir
-l
< INSERTION_THRESHOLD
)
84 insertion_sort(ir
- l
+ 1, l
- 1);
86 if ( stackp
== stack
) break;
88 // Pop stack and begin a new round of partitioning.
94 // Choose median of left, center, and right elements as
95 // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
96 SWAP(arr
[((l
-arr
) + (ir
-arr
))/2-1], l
[0]);
97 SWAP_IF_GREATER(l
[-1], ir
[-1]);
98 SWAP_IF_GREATER(l
[0], ir
[-1]);
99 SWAP_IF_GREATER(l
[-1], l
[0]);
101 // Initialize pointers for partitioning.
105 // Partitioning element.
108 for (;;) { // Beginning of innermost loop.
109 while (*i
++ < a
); // Scan up to find element > a.
110 while (*(j
-- - 2) > a
); // Scan down to find element < a.
111 if (j
< i
) break; // Pointers crossed. Partitioning complete.
112 SWAP(i
[-1], j
[-1]); // Exchange elements.
113 } // End of innermost loop.
115 // Insert partitioning element.
120 // Push pointers to larger subarray on stack,
121 // process smaller subarray immediately.
124 assert(stackp
< stack
+NSTACK
);
143 //--------------------------------------------------------------------------
146 int main( int argc
, char* argv
[] )
148 // Output the input array
149 printArray( "input", DATA_SIZE
, input_data
);
150 printArray( "verify", DATA_SIZE
, verify_data
);
153 // If needed we preallocate everything in the caches
154 sort(DATA_SIZE
, verify_data
);
155 if (verify(DATA_SIZE
, input_data
, input_data
))
161 sort( DATA_SIZE
, input_data
);
164 // Print out the results
165 printArray( "test", DATA_SIZE
, input_data
);
168 return verify( DATA_SIZE
, input_data
, verify_data
);