3 \brief This file contains GKlib's various sorting routines
5 These routines are implemented using the GKSORT macro that is defined
6 in gk_qsort.h and is based on GNU's GLIBC qsort() implementation.
8 Additional sorting routines can be created using the same way that
9 these routines where defined.
13 \version\verbatim $Id: sort.c 10796 2011-09-23 21:33:09Z karypis $ \endverbatim
20 /*************************************************************************/
21 /*! Sorts an array of chars in increasing order */
22 /*************************************************************************/
23 void gk_csorti(size_t n
, char *base
)
25 #define char_lt(a, b) ((*a) < (*b))
26 GK_MKQSORT(char, base
, n
, char_lt
);
31 /*************************************************************************/
32 /*! Sorts an array of chars in decreasing order */
33 /*************************************************************************/
34 void gk_csortd(size_t n
, char *base
)
36 #define char_gt(a, b) ((*a) > (*b))
37 GK_MKQSORT(char, base
, n
, char_gt
);
42 /*************************************************************************/
43 /*! Sorts an array of integers in increasing order */
44 /*************************************************************************/
45 void gk_isorti(size_t n
, int *base
)
47 #define int_lt(a, b) ((*a) < (*b))
48 GK_MKQSORT(int, base
, n
, int_lt
);
53 /*************************************************************************/
54 /*! Sorts an array of integers in decreasing order */
55 /*************************************************************************/
56 void gk_isortd(size_t n
, int *base
)
58 #define int_gt(a, b) ((*a) > (*b))
59 GK_MKQSORT(int, base
, n
, int_gt
);
64 /*************************************************************************/
65 /*! Sorts an array of floats in increasing order */
66 /*************************************************************************/
67 void gk_fsorti(size_t n
, float *base
)
69 #define float_lt(a, b) ((*a) < (*b))
70 GK_MKQSORT(float, base
, n
, float_lt
);
75 /*************************************************************************/
76 /*! Sorts an array of floats in decreasing order */
77 /*************************************************************************/
78 void gk_fsortd(size_t n
, float *base
)
80 #define float_gt(a, b) ((*a) > (*b))
81 GK_MKQSORT(float, base
, n
, float_gt
);
86 /*************************************************************************/
87 /*! Sorts an array of doubles in increasing order */
88 /*************************************************************************/
89 void gk_dsorti(size_t n
, double *base
)
91 #define double_lt(a, b) ((*a) < (*b))
92 GK_MKQSORT(double, base
, n
, double_lt
);
97 /*************************************************************************/
98 /*! Sorts an array of doubles in decreasing order */
99 /*************************************************************************/
100 void gk_dsortd(size_t n
, double *base
)
102 #define double_gt(a, b) ((*a) > (*b))
103 GK_MKQSORT(double, base
, n
, double_gt
);
108 /*************************************************************************/
109 /*! Sorts an array of gk_idx_t in increasing order */
110 /*************************************************************************/
111 void gk_idxsorti(size_t n
, gk_idx_t
*base
)
113 #define idx_lt(a, b) ((*a) < (*b))
114 GK_MKQSORT(gk_idx_t
, base
, n
, idx_lt
);
119 /*************************************************************************/
120 /*! Sorts an array of gk_idx_t in decreasing order */
121 /*************************************************************************/
122 void gk_idxsortd(size_t n
, gk_idx_t
*base
)
124 #define idx_gt(a, b) ((*a) > (*b))
125 GK_MKQSORT(gk_idx_t
, base
, n
, idx_gt
);
132 /*************************************************************************/
133 /*! Sorts an array of gk_ckv_t in increasing order */
134 /*************************************************************************/
135 void gk_ckvsorti(size_t n
, gk_ckv_t
*base
)
137 #define ckey_lt(a, b) ((a)->key < (b)->key)
138 GK_MKQSORT(gk_ckv_t
, base
, n
, ckey_lt
);
143 /*************************************************************************/
144 /*! Sorts an array of gk_ckv_t in decreasing order */
145 /*************************************************************************/
146 void gk_ckvsortd(size_t n
, gk_ckv_t
*base
)
148 #define ckey_gt(a, b) ((a)->key > (b)->key)
149 GK_MKQSORT(gk_ckv_t
, base
, n
, ckey_gt
);
154 /*************************************************************************/
155 /*! Sorts an array of gk_ikv_t in increasing order */
156 /*************************************************************************/
157 void gk_ikvsorti(size_t n
, gk_ikv_t
*base
)
159 #define ikey_lt(a, b) ((a)->key < (b)->key)
160 GK_MKQSORT(gk_ikv_t
, base
, n
, ikey_lt
);
165 /*************************************************************************/
166 /*! Sorts an array of gk_ikv_t in decreasing order */
167 /*************************************************************************/
168 void gk_ikvsortd(size_t n
, gk_ikv_t
*base
)
170 #define ikey_gt(a, b) ((a)->key > (b)->key)
171 GK_MKQSORT(gk_ikv_t
, base
, n
, ikey_gt
);
176 /*************************************************************************/
177 /*! Sorts an array of gk_i32kv_t in increasing order */
178 /*************************************************************************/
179 void gk_i32kvsorti(size_t n
, gk_i32kv_t
*base
)
181 #define ikey_lt(a, b) ((a)->key < (b)->key)
182 GK_MKQSORT(gk_i32kv_t
, base
, n
, ikey_lt
);
187 /*************************************************************************/
188 /*! Sorts an array of gk_i32kv_t in decreasing order */
189 /*************************************************************************/
190 void gk_i32kvsortd(size_t n
, gk_i32kv_t
*base
)
192 #define ikey_gt(a, b) ((a)->key > (b)->key)
193 GK_MKQSORT(gk_i32kv_t
, base
, n
, ikey_gt
);
198 /*************************************************************************/
199 /*! Sorts an array of gk_i64kv_t in increasing order */
200 /*************************************************************************/
201 void gk_i64kvsorti(size_t n
, gk_i64kv_t
*base
)
203 #define ikey_lt(a, b) ((a)->key < (b)->key)
204 GK_MKQSORT(gk_i64kv_t
, base
, n
, ikey_lt
);
209 /*************************************************************************/
210 /*! Sorts an array of gk_i64kv_t in decreasing order */
211 /*************************************************************************/
212 void gk_i64kvsortd(size_t n
, gk_i64kv_t
*base
)
214 #define ikey_gt(a, b) ((a)->key > (b)->key)
215 GK_MKQSORT(gk_i64kv_t
, base
, n
, ikey_gt
);
220 /*************************************************************************/
221 /*! Sorts an array of gk_zkv_t in increasing order */
222 /*************************************************************************/
223 void gk_zkvsorti(size_t n
, gk_zkv_t
*base
)
225 #define zkey_lt(a, b) ((a)->key < (b)->key)
226 GK_MKQSORT(gk_zkv_t
, base
, n
, zkey_lt
);
231 /*************************************************************************/
232 /*! Sorts an array of gk_zkv_t in decreasing order */
233 /*************************************************************************/
234 void gk_zkvsortd(size_t n
, gk_zkv_t
*base
)
236 #define zkey_gt(a, b) ((a)->key > (b)->key)
237 GK_MKQSORT(gk_zkv_t
, base
, n
, zkey_gt
);
242 /*************************************************************************/
243 /*! Sorts an array of gk_fkv_t in increasing order */
244 /*************************************************************************/
245 void gk_fkvsorti(size_t n
, gk_fkv_t
*base
)
247 #define fkey_lt(a, b) ((a)->key < (b)->key)
248 GK_MKQSORT(gk_fkv_t
, base
, n
, fkey_lt
);
253 /*************************************************************************/
254 /*! Sorts an array of gk_fkv_t in decreasing order */
255 /*************************************************************************/
256 void gk_fkvsortd(size_t n
, gk_fkv_t
*base
)
258 #define fkey_gt(a, b) ((a)->key > (b)->key)
259 GK_MKQSORT(gk_fkv_t
, base
, n
, fkey_gt
);
264 /*************************************************************************/
265 /*! Sorts an array of gk_dkv_t in increasing order */
266 /*************************************************************************/
267 void gk_dkvsorti(size_t n
, gk_dkv_t
*base
)
269 #define dkey_lt(a, b) ((a)->key < (b)->key)
270 GK_MKQSORT(gk_dkv_t
, base
, n
, dkey_lt
);
275 /*************************************************************************/
276 /*! Sorts an array of gk_fkv_t in decreasing order */
277 /*************************************************************************/
278 void gk_dkvsortd(size_t n
, gk_dkv_t
*base
)
280 #define dkey_gt(a, b) ((a)->key > (b)->key)
281 GK_MKQSORT(gk_dkv_t
, base
, n
, dkey_gt
);
286 /*************************************************************************/
287 /*! Sorts an array of gk_skv_t in increasing order */
288 /*************************************************************************/
289 void gk_skvsorti(size_t n
, gk_skv_t
*base
)
291 #define skey_lt(a, b) (strcmp((a)->key, (b)->key) < 0)
292 GK_MKQSORT(gk_skv_t
, base
, n
, skey_lt
);
297 /*************************************************************************/
298 /*! Sorts an array of gk_skv_t in decreasing order */
299 /*************************************************************************/
300 void gk_skvsortd(size_t n
, gk_skv_t
*base
)
302 #define skey_gt(a, b) (strcmp((a)->key, (b)->key) > 0)
303 GK_MKQSORT(gk_skv_t
, base
, n
, skey_gt
);
308 /*************************************************************************/
309 /*! Sorts an array of gk_idxkv_t in increasing order */
310 /*************************************************************************/
311 void gk_idxkvsorti(size_t n
, gk_idxkv_t
*base
)
313 #define idxkey_lt(a, b) ((a)->key < (b)->key)
314 GK_MKQSORT(gk_idxkv_t
, base
, n
, idxkey_lt
);
319 /*************************************************************************/
320 /*! Sorts an array of gk_idxkv_t in decreasing order */
321 /*************************************************************************/
322 void gk_idxkvsortd(size_t n
, gk_idxkv_t
*base
)
324 #define idxkey_gt(a, b) ((a)->key > (b)->key)
325 GK_MKQSORT(gk_idxkv_t
, base
, n
, idxkey_gt
);