forked from dlang/phobos
-
Notifications
You must be signed in to change notification settings - Fork 1
/
qsort.d
157 lines (133 loc) · 4.24 KB
/
qsort.d
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
154
155
156
/*
Copyright Prototronics, 1987
Totem Lake P.O. 8117
Kirkland, Washington 98034
(206) 820-1972
Licensed to Digital Mars.
June 11, 1987 from Ray Gardner's
Denver, Colorado) public domain version
*/
/*
** Sorts an array starting at base, of length nbr_elements, each
** element of size width_bytes, ordered via compare_function; which
** is called as (*comp_fp)(ptr_to_element1, ptr_to_element2)
** and returns < 0 if element1 < element2, 0 if element1 = element2,
** > 0 if element1 > element2. Most of the refinements are due to
** R. Sedgewick. See "Implementing Quicksort Programs", Comm. ACM,
** Oct. 1978, and Corrigendum, Comm. ACM, June 1979.
*/
//debug=qsort; // uncomment to turn on debugging printf's
import c.stdio;
import c.stdlib;
import string;
import outofmemory;
struct Array
{
int length;
void *ptr;
}
private const int _maxspan = 7; // subarrays of _maxspan or fewer elements
// will be sorted by a simple insertion sort
/* Adjust _maxspan according to relative cost of a swap and a compare. Reduce
_maxspan (not less than 1) if a swap is very expensive such as when you have
an array of large structures to be sorted, rather than an array of pointers to
structures. The default value is optimized for a high cost for compares. */
extern (C) Array _adSort(Array a, TypeInfo ti)
{
byte* base;
byte*[40] stack; // stack
byte** sp; // stack pointer
byte* i, j, limit; // scan and limit pointers
uint thresh; // size of _maxspan elements in bytes
uint width = ti.tsize();
base = (byte *)a.ptr;
thresh = _maxspan * width; // init threshold
sp = stack; // init stack pointer
limit = base + a.length * width; // pointer past end of array
while (1) // repeat until done then return
{
while (limit - base > thresh) // if more than _maxspan elements
{
//swap middle, base
ti.swap(((uint)(limit - base) >> 1) -
((((uint)(limit - base) >> 1)) % width) + base, base);
i = base + width; // i scans from left to right
j = limit - width; // j scans from right to left
if (ti.compare(i, j) > 0) // Sedgewick's
ti.swap(i, j); // three-element sort
if (ti.compare(base, j) > 0) // sets things up
ti.swap(base, j); // so that
if (ti.compare(i, base) > 0) // *i <= *base <= *j
ti.swap(i, base); // *base is the pivot element
while (1)
{
do // move i right until *i >= pivot
i += width;
while (ti.compare(i, base) < 0);
do // move j left until *j <= pivot
j -= width;
while (ti.compare(j, base) > 0);
if (i > j) // break loop if pointers crossed
break;
ti.swap(i, j); // else swap elements, keep scanning
}
ti.swap(base, j); // move pivot into correct place
if (j - base > limit - i) // if left subarray is larger...
{
sp[0] = base; // stack left subarray base
sp[1] = j; // and limit
base = i; // sort the right subarray
}
else // else right subarray is larger
{
sp[0] = i; // stack right subarray base
sp[1] = limit; // and limit
limit = j; // sort the left subarray
}
sp += 2; // increment stack pointer
assert(sp < (byte**)stack + stack.length);
}
// Insertion sort on remaining subarray
i = base + width;
while (i < limit)
{
j = i;
while (j > base && ti.compare(j - width, j) > 0)
{
ti.swap(j - width, j);
j -= width;
}
i += width;
}
if (sp > stack) // if any entries on stack...
{
sp -= 2; // pop the base and limit
base = sp[0];
limit = sp[1];
}
else // else stack empty, all done
return a;
}
}
unittest
{
debug(qsort) printf("array.sort.unittest()\n");
int a[] = new int[10];
a[0] = 23;
a[1] = 1;
a[2] = 64;
a[3] = 5;
a[4] = 6;
a[5] = 5;
a[6] = 17;
a[7] = 3;
a[8] = 0;
a[9] = -1;
a.sort;
for (int i = 0; i < a.length - 1; i++)
{
//printf("i = %d", i);
//printf(" %d %d\n", a[i], a[i + 1]);
assert(a[i] <= a[i + 1]);
}
}