This repository has been archived by the owner on Oct 12, 2022. It is now read-only.
/
qsort.d
162 lines (136 loc) · 5.08 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
157
158
159
160
161
/*
Portions of this file are:
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
Use qsort2.d instead of this file if a redistributable version of
_adSort() is required.
*/
module rt.qsort;
/*
** 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 core.stdc.stdlib;
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) void[] _adSort(void[] a, TypeInfo ti)
{
byte*[40] stackbuf = void; // initial stack buffer
auto stack = stackbuf[0..$]; // stack
auto sp = stack.ptr; // stack pointer
auto width = ti.tsize;
auto base = cast(byte *)a.ptr;
auto thresh = _maxspan * width; // size of _maxspan elements in bytes
auto 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((cast(uint)(limit - base) >> 1) -
(((cast(uint)(limit - base) >> 1)) % width) + base, base);
auto i = base + width; // i scans from left to right
auto 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
if (sp == stack.ptr + stack.length)
{
// Double the size of stack[]
auto newstack = cast(byte**)alloca(stack.length * 2 * (*sp).sizeof);
newstack[0..stack.length] = stack[];
sp = &newstack[stack.length];
stack = newstack[0..stack.length * 2];
}
}
// Insertion sort on remaining subarray
auto i = base + width;
while (i < limit)
{
auto j = i;
while (j > base && ti.compare(j - width, j) > 0)
{
ti.swap(j - width, j);
j -= width;
}
i += width;
}
if (sp > stack.ptr) // 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 *cast(void[]*)(&a);
}
assert(0);
}
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]);
}
auto b = new uint[0xFF_FFFF];
b.sort;
}