Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
myqsort.c
Go to the documentation of this file.
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 **************************************************************************/
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 
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 **************************************************************************/
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 
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 **************************************************************************/
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 
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 **************************************************************************/
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 
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 }
#define iidxsort
Definition: rename.h:287
#define ikeyvalsort
Definition: rename.h:290
#define ikeysort
Definition: rename.h:289
idxtype key
Definition: struct.h:31
int idxtype
Definition: struct.h:19
#define swap(a, b, c)
Definition: mg.c:184
#define THRESH
Definition: myqsort.c:17
#define iintsort
Definition: rename.h:288
#define min(a, b)
Definition: refMPIluBack.c:56
idxtype val
Definition: struct.h:32
#define max(a, b)
Definition: cannonAsync.c:47
#define MTHRESH
Definition: myqsort.c:18