Hitmap 1.3
 All Data Structures Namespaces Files Functions Variables Typedefs Friends Macros Groups Pages
bucketsort.c
Go to the documentation of this file.
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  * $Id: bucketsort.c,v 1.1 1998/11/27 17:59:11 karypis Exp $
13  *
14  */
15 
16 #include <metis.h>
17 
18 
19 
20 /*************************************************************************
21 * This function uses simple counting sort to return a permutation array
22 * corresponding to the sorted order. The keys are assumed to start from
23 * 0 and they are positive. This sorting is used during matching.
24 **************************************************************************/
25 void BucketSortKeysInc(int n, int max, idxtype *keys, idxtype *tperm, idxtype *perm)
26 {
27  int i, ii;
28  idxtype *counts;
29 
30  counts = idxsmalloc(max+2, 0, "BucketSortKeysInc: counts");
31 
32  for (i=0; i<n; i++)
33  counts[keys[i]]++;
34  MAKECSR(i, max+1, counts);
35 
36  for (ii=0; ii<n; ii++) {
37  i = tperm[ii];
38  perm[counts[keys[i]]++] = i;
39  }
40 
41  free(counts);
42 }
43 
#define BucketSortKeysInc
Definition: rename.h:22
#define MAKECSR(i, n, a)
Definition: macros.h:91
int idxtype
Definition: struct.h:19
#define idxsmalloc
Definition: rename.h:386
#define max(a, b)
Definition: cannonAsync.c:47