source: inundation/pymetis/metis-4.0/Lib/myqsort.c @ 2051

Last change on this file since 2051 was 2051, checked in by jack, 19 years ago

Python interface to metis. Currently provides only the
METIS_PartMeshNodal function, since that is what is currently needed for partitioning.
Module name is metis.
File size: 11.2 KB
Line 
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
23static void siqst(idxtype *, idxtype *);
24static void iiqst(int *, int *);
25static void keyiqst(KeyValueType *, KeyValueType *);
26static void keyvaliqst(KeyValueType *, KeyValueType *);
27
28
29/*************************************************************************
30* Entry point of idxtype increasing sort
31**************************************************************************/
32void 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
77static 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      }
132swap:
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**************************************************************************/
161void 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
207static 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      }
262swap:
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**************************************************************************/
291void 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
345static 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      }
399swap:
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**************************************************************************/
427void 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
473static 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      }
527swap:
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}
Note: See TracBrowser for help on using the repository browser.