source: buchla-68k/orig/CLIBRARY/QSORT.C@ 73dd55f

Last change on this file since 73dd55f was 3ae31e9, checked in by Thomas Lopatic <thomas@…>, 8 years ago

Imported original source code.
  • Property mode set to 100755
File size: 3.4 KB
Line 
1/*
2 =============================================================================
3 qsort.c -- quicksort algorithm
4 Version 2 -- 1989-01-12 -- D.N. Lynx Crowe
5 =============================================================================
6*/
7
8#include "stddefs.h"
9
10static unsigned qscnt; /* size of an element */
11static int (*qscmp)(); /* comparison function */
12
13/*
14 =============================================================================
15 qsexch() -- exchange two elements
16 =============================================================================
17*/
18
19static
20qsexch(ip, jp)
21register char *ip, *jp;
22{
23 register unsigned n;
24 register char c;
25
26 n = qscnt;
27
28 do {
29 c = *ip;
30 *ip++ = *jp;
31 *jp++ = c;
32
33 } while (--n);
34}
35
36/*
37
38*/
39
40/*
41 =============================================================================
42 qstexc() - circular exchange of 3 elements
43 =============================================================================
44*/
45
46static
47qstexc(ip, jp, kp)
48register char *ip, *jp, *kp;
49{
50 register unsigned n;
51 register char c;
52
53 n = qscnt;
54
55 do {
56
57 c = *ip;
58 *ip++ = *kp;
59 *kp++ = *jp;
60 *jp++ = c;
61
62 } while (--n);
63}
64
65/*
66
67*/
68
69/*
70 =============================================================================
71 qsort1() -- Quicksort algorithm driver
72 =============================================================================
73*/
74
75static
76qsort1(a, l)
77char *a, *l;
78{
79 register char *hp, *i, *j;
80 register unsigned es, n;
81 register int c;
82 char *lp;
83
84 es = qscnt;
85
86start:
87 if ((n = (long)l - (long)a) LE es)
88 return;
89
90 n = es * (n / (2 * es));
91 hp = lp = a + n;
92 i = a;
93 j = l - es;
94
95 while (TRUE) {
96
97 if (i < lp) {
98
99 if ((c = (*qscmp)(i, lp)) EQ 0) {
100
101 qsexch(i, lp -= es);
102 continue;
103 }
104
105 if (c < 0) {
106
107 i += es;
108 continue;
109 }
110 }
111
112/*
113
114*/
115
116loop:
117 if (j > hp) {
118
119 if ((c = (*qscmp)(hp, j)) EQ 0) {
120
121 qsexch(hp += es, j);
122 goto loop;
123 }
124
125 if (c > 0) {
126
127 if (i EQ lp) {
128
129 qstexc(i, hp += es, j);
130 i = lp += es;
131 goto loop;
132 }
133
134 qsexch(i, j);
135 j -= es;
136 i += es;
137 continue;
138 }
139
140 j -= es;
141 goto loop;
142 }
143
144 if (i EQ lp) {
145
146 if (((long)lp - (long)a) GE ((long)l - (long)hp)) {
147
148 qsort1(hp + es, l);
149 l = lp;
150
151 } else {
152
153 qsort1(a, lp);
154 a = hp + es;
155 }
156
157 goto start;
158 }
159
160 qstexc(j, lp -= es, i);
161 j = hp -= es;
162 }
163}
164
165/*
166
167*/
168
169/*
170 =============================================================================
171 qsort(base, n, esize, comp) -- Quicksort algorithm
172
173 base pointer to the element at the base of the table
174
175 n number of elements in the table
176
177 esize element size (sizeof (*base))
178
179 comp comparison function: comp(e1, e2)
180
181 where: e1 and e2 are pointers to the elements to compare
182
183 comp() must return an integer which describes the result
184 of the comparison, as follows:
185
186 < 0 e1 < e2 (eg. -1)
187 = 0 e1 = e2
188 > 0 e1 > e2 (eg. +1)
189
190 The string function strcmp(e1, e2), for example, might be
191 suitable for use with qsort (assuming equal length strings).
192 =============================================================================
193*/
194
195qsort(base, n, esize, fc)
196char *base;
197unsigned n;
198unsigned esize;
199int (*fc)();
200{
201 qscmp = fc;
202 qscnt = esize;
203 qsort1(base, base + ((long)n * (long)esize));
204}
Note: See TracBrowser for help on using the repository browser.