1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
|
// See LICENSE for license details.
//**************************************************************************
// Quicksort benchmark
//--------------------------------------------------------------------------
//
// This benchmark uses quicksort to sort an array of integers. The
// implementation is largely adapted from Numerical Recipes for C. The
// input data (and reference data) should be generated using the
// qsort_gendata.pl perl script and dumped to a file named
// dataset1.h.
#include "util.h"
#include <string.h>
#include <assert.h>
// The INSERTION_THRESHOLD is the size of the subarray when the
// algorithm switches to using an insertion sort instead of
// quick sort.
#define INSERTION_THRESHOLD 10
// NSTACK is the required auxiliary storage.
// It must be at least 2*lg(DATA_SIZE)
#define NSTACK 50
//--------------------------------------------------------------------------
// Input/Reference Data
#define type int
#include "dataset1.h"
// Swap macro for swapping two values.
#define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
#define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
//--------------------------------------------------------------------------
// Quicksort function
static void insertion_sort(size_t n, type arr[])
{
type *i, *j;
type value;
for (i = arr+1; i < arr+n; i++)
{
value = *i;
j = i;
while (value < *(j-1))
{
*j = *(j-1);
if (--j == arr)
break;
}
*j = value;
}
}
static void selection_sort(size_t n, type arr[])
{
for (type* i = arr; i < arr+n-1; i++)
for (type* j = i+1; j < arr+n; j++)
SWAP_IF_GREATER(*i, *j);
}
void sort(size_t n, type arr[])
{
type* ir = arr+n;
type* l = arr+1;
type* stack[NSTACK];
type** stackp = stack;
for (;;)
{
// Insertion sort when subarray small enough.
if ( ir-l < INSERTION_THRESHOLD )
{
insertion_sort(ir - l + 1, l - 1);
if ( stackp == stack ) break;
// Pop stack and begin a new round of partitioning.
ir = *stackp--;
l = *stackp--;
}
else
{
// Choose median of left, center, and right elements as
// partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
SWAP_IF_GREATER(l[-1], ir[-1]);
SWAP_IF_GREATER(l[0], ir[-1]);
SWAP_IF_GREATER(l[-1], l[0]);
// Initialize pointers for partitioning.
type* i = l+1;
type* j = ir;
// Partitioning element.
type a = l[0];
for (;;) { // Beginning of innermost loop.
while (*i++ < a); // Scan up to find element > a.
while (*(j-- - 2) > a); // Scan down to find element < a.
if (j < i) break; // Pointers crossed. Partitioning complete.
SWAP(i[-1], j[-1]); // Exchange elements.
} // End of innermost loop.
// Insert partitioning element.
l[0] = j[-1];
j[-1] = a;
stackp += 2;
// Push pointers to larger subarray on stack,
// process smaller subarray immediately.
if ( ir-i+1 >= j-l )
{
stackp[0] = ir;
stackp[-1] = i;
ir = j-1;
}
else
{
stackp[0] = j-1;
stackp[-1] = l;
l = i;
}
}
}
}
//--------------------------------------------------------------------------
// Main
int main( int argc, char* argv[] )
{
#if PREALLOCATE
// If needed we preallocate everything in the caches
sort(DATA_SIZE, verify_data);
if (verify(DATA_SIZE, input_data, input_data))
return 1;
#endif
// Do the sort
setStats(1);
sort( DATA_SIZE, input_data );
setStats(0);
// Check the results
return verify( DATA_SIZE, input_data, verify_data );
}
|
