1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * myqsort.c
5 *
6 * This file contains a fast idxtype increasing qsort algorithm.
7 * Addopted from TeX
8 *
9 * Started 10/18/96
10 * George
11 *
12 * $Id: myqsort.c,v 1.1 1998/11/27 17:59:27 karypis Exp $
13 */
14
15 #include "metis.h" /* only for type declarations */
16
17 #define THRESH 1 /* threshold for insertion */
18 #define MTHRESH 6 /* threshold for median */
19
20
21
22
23 static void siqst(idxtype *, idxtype *);
24 static void iiqst(int *, int *);
25 static void keyiqst(KeyValueType *, KeyValueType *);
26 static void keyvaliqst(KeyValueType *, KeyValueType *);
27
28
29 /*************************************************************************
30 * Entry point of idxtype increasing sort
31 **************************************************************************/
iidxsort(int n,idxtype * base)32 void iidxsort(int n, idxtype *base)
33 {
34 register idxtype *i;
35 register idxtype *j;
36 register idxtype *lo;
37 register idxtype *hi;
38 register idxtype *min;
39 register idxtype c;
40 idxtype *max;
41
42 if (n <= 1)
43 return;
44
45 max = base + n;
46
47 if (n >= THRESH) {
48 siqst(base, max);
49 hi = base + THRESH;
50 }
51 else
52 hi = max;
53
54 for (j = lo = base; lo++ < hi;) {
55 if (*j > *lo)
56 j = lo;
57 }
58 if (j != base) { /* swap j into place */
59 c = *base;
60 *base = *j;
61 *j = c;
62 }
63
64 for (min = base; (hi = min += 1) < max;) {
65 while (*(--hi) > *min);
66 if ((hi += 1) != min) {
67 for (lo = min + 1; --lo >= min;) {
68 c = *lo;
69 for (i = j = lo; (j -= 1) >= hi; i = j)
70 *i = *j;
71 *i = c;
72 }
73 }
74 }
75 }
76
siqst(idxtype * base,idxtype * max)77 static void siqst(idxtype *base, idxtype *max)
78 {
79 register idxtype *i;
80 register idxtype *j;
81 register idxtype *jj;
82 register idxtype *mid;
83 register int ii;
84 register idxtype c;
85 idxtype *tmp;
86 int lo;
87 int hi;
88
89 lo = max - base; /* number of elements as idxtype */
90 do {
91 mid = base + ((unsigned) lo>>1);
92 if (lo >= MTHRESH) {
93 j = (*base > *mid ? base : mid);
94 tmp = max - 1;
95 if (*j > *tmp) {
96 j = (j == base ? mid : base); /* switch to first loser */
97 if (*j < *tmp)
98 j = tmp;
99 }
100
101 if (j != mid) { /* SWAP */
102 c = *mid;
103 *mid = *j;
104 *j = c;
105 }
106 }
107
108 /* Semi-standard quicksort partitioning/swapping */
109 for (i = base, j = max - 1;;) {
110 while (i < mid && *i <= *mid)
111 i++;
112 while (j > mid) {
113 if (*mid <= *j) {
114 j--;
115 continue;
116 }
117 tmp = i + 1; /* value of i after swap */
118 if (i == mid) /* j <-> mid, new mid is j */
119 mid = jj = j;
120 else /* i <-> j */
121 jj = j--;
122 goto swap;
123 }
124
125 if (i == mid)
126 break;
127 else { /* i <-> mid, new mid is i */
128 jj = mid;
129 tmp = mid = i; /* value of i after swap */
130 j--;
131 }
132 swap:
133 c = *i;
134 *i = *jj;
135 *jj = c;
136 i = tmp;
137 }
138
139 i = (j = mid) + 1;
140 if ((lo = j - base) <= (hi = max - i)) {
141 if (lo >= THRESH)
142 siqst(base, j);
143 base = i;
144 lo = hi;
145 }
146 else {
147 if (hi >= THRESH)
148 siqst(i, max);
149 max = j;
150 }
151 } while (lo >= THRESH);
152 }
153
154
155
156
157
158 /*************************************************************************
159 * Entry point of int increasing sort
160 **************************************************************************/
iintsort(int n,int * base)161 void iintsort(int n, int *base)
162 {
163 register int *i;
164 register int *j;
165 register int *lo;
166 register int *hi;
167 register int *min;
168 register int c;
169 int *max;
170
171 if (n <= 1)
172 return;
173
174 max = base + n;
175
176 if (n >= THRESH) {
177 iiqst(base, max);
178 hi = base + THRESH;
179 }
180 else
181 hi = max;
182
183 for (j = lo = base; lo++ < hi;) {
184 if (*j > *lo)
185 j = lo;
186 }
187 if (j != base) { /* swap j into place */
188 c = *base;
189 *base = *j;
190 *j = c;
191 }
192
193 for (min = base; (hi = min += 1) < max;) {
194 while (*(--hi) > *min);
195 if ((hi += 1) != min) {
196 for (lo = min + 1; --lo >= min;) {
197 c = *lo;
198 for (i = j = lo; (j -= 1) >= hi; i = j)
199 *i = *j;
200 *i = c;
201 }
202 }
203 }
204 }
205
206
iiqst(int * base,int * max)207 static void iiqst(int *base, int *max)
208 {
209 register int *i;
210 register int *j;
211 register int *jj;
212 register int *mid;
213 register int ii;
214 register int c;
215 int *tmp;
216 int lo;
217 int hi;
218
219 lo = max - base; /* number of elements as ints */
220 do {
221 mid = base + ((unsigned) lo>>1);
222 if (lo >= MTHRESH) {
223 j = (*base > *mid ? base : mid);
224 tmp = max - 1;
225 if (*j > *tmp) {
226 j = (j == base ? mid : base); /* switch to first loser */
227 if (*j < *tmp)
228 j = tmp;
229 }
230
231 if (j != mid) { /* SWAP */
232 c = *mid;
233 *mid = *j;
234 *j = c;
235 }
236 }
237
238 /* Semi-standard quicksort partitioning/swapping */
239 for (i = base, j = max - 1;;) {
240 while (i < mid && *i <= *mid)
241 i++;
242 while (j > mid) {
243 if (*mid <= *j) {
244 j--;
245 continue;
246 }
247 tmp = i + 1; /* value of i after swap */
248 if (i == mid) /* j <-> mid, new mid is j */
249 mid = jj = j;
250 else /* i <-> j */
251 jj = j--;
252 goto swap;
253 }
254
255 if (i == mid)
256 break;
257 else { /* i <-> mid, new mid is i */
258 jj = mid;
259 tmp = mid = i; /* value of i after swap */
260 j--;
261 }
262 swap:
263 c = *i;
264 *i = *jj;
265 *jj = c;
266 i = tmp;
267 }
268
269 i = (j = mid) + 1;
270 if ((lo = j - base) <= (hi = max - i)) {
271 if (lo >= THRESH)
272 iiqst(base, j);
273 base = i;
274 lo = hi;
275 }
276 else {
277 if (hi >= THRESH)
278 iiqst(i, max);
279 max = j;
280 }
281 } while (lo >= THRESH);
282 }
283
284
285
286
287
288 /*************************************************************************
289 * Entry point of KeyVal increasing sort, ONLY key part
290 **************************************************************************/
ikeysort(int n,KeyValueType * base)291 void ikeysort(int n, KeyValueType *base)
292 {
293 register KeyValueType *i;
294 register KeyValueType *j;
295 register KeyValueType *lo;
296 register KeyValueType *hi;
297 register KeyValueType *min;
298 register KeyValueType c;
299 KeyValueType *max;
300
301 if (n <= 1)
302 return;
303
304 max = base + n;
305
306 if (n >= THRESH) {
307 keyiqst(base, max);
308 hi = base + THRESH;
309 }
310 else
311 hi = max;
312
313 for (j = lo = base; lo++ < hi;) {
314 if (j->key > lo->key)
315 j = lo;
316 }
317 if (j != base) { /* swap j into place */
318 c = *base;
319 *base = *j;
320 *j = c;
321 }
322
323 for (min = base; (hi = min += 1) < max;) {
324 while ((--hi)->key > min->key);
325 if ((hi += 1) != min) {
326 for (lo = min + 1; --lo >= min;) {
327 c = *lo;
328 for (i = j = lo; (j -= 1) >= hi; i = j)
329 *i = *j;
330 *i = c;
331 }
332 }
333 }
334
335 /* Sanity check */
336 {
337 int i;
338 for (i=0; i<n-1; i++)
339 if (base[i].key > base[i+1].key)
340 printf("Something went wrong!\n");
341 }
342 }
343
344
keyiqst(KeyValueType * base,KeyValueType * max)345 static void keyiqst(KeyValueType *base, KeyValueType *max)
346 {
347 register KeyValueType *i;
348 register KeyValueType *j;
349 register KeyValueType *jj;
350 register KeyValueType *mid;
351 register KeyValueType c;
352 KeyValueType *tmp;
353 int lo;
354 int hi;
355
356 lo = (max - base)>>1; /* number of elements as KeyValueType */
357 do {
358 mid = base + ((unsigned) lo>>1);
359 if (lo >= MTHRESH) {
360 j = (base->key > mid->key ? base : mid);
361 tmp = max - 1;
362 if (j->key > tmp->key) {
363 j = (j == base ? mid : base); /* switch to first loser */
364 if (j->key < tmp->key)
365 j = tmp;
366 }
367
368 if (j != mid) { /* SWAP */
369 c = *mid;
370 *mid = *j;
371 *j = c;
372 }
373 }
374
375 /* Semi-standard quicksort partitioning/swapping */
376 for (i = base, j = max - 1;;) {
377 while (i < mid && i->key <= mid->key)
378 i++;
379 while (j > mid) {
380 if (mid->key <= j->key) {
381 j--;
382 continue;
383 }
384 tmp = i + 1; /* value of i after swap */
385 if (i == mid) /* j <-> mid, new mid is j */
386 mid = jj = j;
387 else /* i <-> j */
388 jj = j--;
389 goto swap;
390 }
391
392 if (i == mid)
393 break;
394 else { /* i <-> mid, new mid is i */
395 jj = mid;
396 tmp = mid = i; /* value of i after swap */
397 j--;
398 }
399 swap:
400 c = *i;
401 *i = *jj;
402 *jj = c;
403 i = tmp;
404 }
405
406 i = (j = mid) + 1;
407 if ((lo = (j - base)>>1) <= (hi = (max - i)>>1)) {
408 if (lo >= THRESH)
409 keyiqst(base, j);
410 base = i;
411 lo = hi;
412 }
413 else {
414 if (hi >= THRESH)
415 keyiqst(i, max);
416 max = j;
417 }
418 } while (lo >= THRESH);
419 }
420
421
422
423
424 /*************************************************************************
425 * Entry point of KeyVal increasing sort, BOTH key and val part
426 **************************************************************************/
ikeyvalsort(int n,KeyValueType * base)427 void ikeyvalsort(int n, KeyValueType *base)
428 {
429 register KeyValueType *i;
430 register KeyValueType *j;
431 register KeyValueType *lo;
432 register KeyValueType *hi;
433 register KeyValueType *min;
434 register KeyValueType c;
435 KeyValueType *max;
436
437 if (n <= 1)
438 return;
439
440 max = base + n;
441
442 if (n >= THRESH) {
443 keyvaliqst(base, max);
444 hi = base + THRESH;
445 }
446 else
447 hi = max;
448
449 for (j = lo = base; lo++ < hi;) {
450 if ((j->key > lo->key) || (j->key == lo->key && j->val > lo->val))
451 j = lo;
452 }
453 if (j != base) { /* swap j into place */
454 c = *base;
455 *base = *j;
456 *j = c;
457 }
458
459 for (min = base; (hi = min += 1) < max;) {
460 while ((--hi)->key > min->key || (hi->key == min->key && hi->val > min->val));
461 if ((hi += 1) != min) {
462 for (lo = min + 1; --lo >= min;) {
463 c = *lo;
464 for (i = j = lo; (j -= 1) >= hi; i = j)
465 *i = *j;
466 *i = c;
467 }
468 }
469 }
470 }
471
472
keyvaliqst(KeyValueType * base,KeyValueType * max)473 static void keyvaliqst(KeyValueType *base, KeyValueType *max)
474 {
475 register KeyValueType *i;
476 register KeyValueType *j;
477 register KeyValueType *jj;
478 register KeyValueType *mid;
479 register KeyValueType c;
480 KeyValueType *tmp;
481 int lo;
482 int hi;
483
484 lo = (max - base)>>1; /* number of elements as KeyValueType */
485 do {
486 mid = base + ((unsigned) lo>>1);
487 if (lo >= MTHRESH) {
488 j = (base->key > mid->key || (base->key == mid->key && base->val > mid->val) ? base : mid);
489 tmp = max - 1;
490 if (j->key > tmp->key || (j->key == tmp->key && j->val > tmp->val)) {
491 j = (j == base ? mid : base); /* switch to first loser */
492 if (j->key < tmp->key || (j->key == tmp->key && j->val < tmp->val))
493 j = tmp;
494 }
495
496 if (j != mid) { /* SWAP */
497 c = *mid;
498 *mid = *j;
499 *j = c;
500 }
501 }
502
503 /* Semi-standard quicksort partitioning/swapping */
504 for (i = base, j = max - 1;;) {
505 while (i < mid && (i->key < mid->key || (i->key == mid->key && i->val <= mid->val)))
506 i++;
507 while (j > mid) {
508 if (mid->key < j->key || (mid->key == j->key && mid->val <= j->val)) {
509 j--;
510 continue;
511 }
512 tmp = i + 1; /* value of i after swap */
513 if (i == mid) /* j <-> mid, new mid is j */
514 mid = jj = j;
515 else /* i <-> j */
516 jj = j--;
517 goto swap;
518 }
519
520 if (i == mid)
521 break;
522 else { /* i <-> mid, new mid is i */
523 jj = mid;
524 tmp = mid = i; /* value of i after swap */
525 j--;
526 }
527 swap:
528 c = *i;
529 *i = *jj;
530 *jj = c;
531 i = tmp;
532 }
533
534 i = (j = mid) + 1;
535 if ((lo = (j - base)>>1) <= (hi = (max - i)>>1)) {
536 if (lo >= THRESH)
537 keyvaliqst(base, j);
538 base = i;
539 lo = hi;
540 }
541 else {
542 if (hi >= THRESH)
543 keyvaliqst(i, max);
544 max = j;
545 }
546 } while (lo >= THRESH);
547 }
548