forked from Stichting-MINIX-Research-Foundation/minix
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathqsort.c
More file actions
executable file
·139 lines (130 loc) · 3.26 KB
/
Copy pathqsort.c
File metadata and controls
executable file
·139 lines (130 loc) · 3.26 KB
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
/*
* (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
* See the copyright notice in the ACK home directory, in the file "Copyright".
*/
/* $Header$ */
#include <stdlib.h>
static void qsort1(char *, char *, size_t);
static int (*qcompar)(const char *, const char *);
static void qexchange(char *, char *, size_t);
static void q3exchange(char *, char *, char *, size_t);
void
qsort(void *base, size_t nel, size_t width,
int (*compar)(const void *, const void *))
{
/* when nel is 0, the expression '(nel - 1) * width' is wrong */
if (!nel) return;
qcompar = (int (*)(const char *, const char *)) compar;
qsort1(base, (char *)base + (nel - 1) * width, width);
}
static void
qsort1(char *a1, char *a2, register size_t width)
{
register char *left, *right;
register char *lefteq, *righteq;
int cmp;
for (;;) {
if (a2 <= a1) return;
left = a1;
right = a2;
lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));
/*
Pick an element in the middle of the array.
We will collect the equals around it.
"lefteq" and "righteq" indicate the left and right
bounds of the equals respectively.
Smaller elements end up left of it, larger elements end
up right of it.
*/
again:
while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
if (cmp < 0) {
/* leave it where it is */
left += width;
}
else {
/* equal, so exchange with the element to
the left of the "equal"-interval.
*/
lefteq -= width;
qexchange(left, lefteq, width);
}
}
while (right > righteq) {
if ((cmp = (*qcompar)(right, righteq)) < 0) {
/* smaller, should go to left part
*/
if (left < lefteq) {
/* yes, we had a larger one at the
left, so we can just exchange
*/
qexchange(left, right, width);
left += width;
right -= width;
goto again;
}
/* no more room at the left part, so we
move the "equal-interval" one place to the
right, and the smaller element to the
left of it.
This is best expressed as a three-way
exchange.
*/
righteq += width;
q3exchange(left, righteq, right, width);
lefteq += width;
left = lefteq;
}
else if (cmp == 0) {
/* equal, so exchange with the element to
the right of the "equal-interval"
*/
righteq += width;
qexchange(right, righteq, width);
}
else /* just leave it */ right -= width;
}
if (left < lefteq) {
/* larger element to the left, but no more room,
so move the "equal-interval" one place to the
left, and the larger element to the right
of it.
*/
lefteq -= width;
q3exchange(right, lefteq, left, width);
righteq -= width;
right = righteq;
goto again;
}
/* now sort the "smaller" part */
qsort1(a1, lefteq - width, width);
/* and now the larger, saving a subroutine call
because of the for(;;)
*/
a1 = righteq + width;
}
/*NOTREACHED*/
}
static void
qexchange(register char *p, register char *q,
register size_t n)
{
register int c;
while (n-- > 0) {
c = *p;
*p++ = *q;
*q++ = c;
}
}
static void
q3exchange(register char *p, register char *q, register char *r,
register size_t n)
{
register int c;
while (n-- > 0) {
c = *p;
*p++ = *r;
*r++ = *q;
*q++ = c;
}
}