1 /*
2 * Copyright 1997, Regents of the University of Minnesota
3 *
4 * bucketsort.c
5 *
6 * This file contains code that implement a variety of counting sorting
7 * algorithms
8 *
9 * Started 7/25/97
10 * George
11 *
12 */
13
14 #include "metislib.h"
15
16
17
18 /*************************************************************************
19 * This function uses simple counting sort to return a permutation array
20 * corresponding to the sorted order. The keys are arsumed to start from
21 * 0 and they are positive. This sorting is used during matching.
22 **************************************************************************/
BucketSortKeysInc(ctrl_t * ctrl,idx_t n,idx_t max,idx_t * keys,idx_t * tperm,idx_t * perm)23 void BucketSortKeysInc(ctrl_t *ctrl, idx_t n, idx_t max, idx_t *keys,
24 idx_t *tperm, idx_t *perm)
25 {
26 idx_t i, ii;
27 idx_t *counts;
28
29 WCOREPUSH;
30
31 counts = iset(max+2, 0, iwspacemalloc(ctrl, max+2));
32
33 for (i=0; i<n; i++)
34 counts[keys[i]]++;
35 MAKECSR(i, max+1, counts);
36
37 for (ii=0; ii<n; ii++) {
38 i = tperm[ii];
39 perm[counts[keys[i]]++] = i;
40 }
41
42 WCOREPOP;
43 }
44
45