1 /*!
2 \file sort.c
3 \brief This file contains GKlib's various sorting routines
4
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.
7
8 Additional sorting routines can be created using the same way that
9 these routines where defined.
10
11 \date Started 4/4/07
12 \author George
13 \version\verbatim $Id: sort.c 10796 2011-09-23 21:33:09Z karypis $ \endverbatim
14 */
15
16 #include <GKlib.h>
17
18
19
20 /*************************************************************************/
21 /*! Sorts an array of chars in increasing order */
22 /*************************************************************************/
gk_csorti(size_t n,char * base)23 void gk_csorti(size_t n, char *base)
24 {
25 #define char_lt(a, b) ((*a) < (*b))
26 GK_MKQSORT(char, base, n, char_lt);
27 #undef char_lt
28 }
29
30
31 /*************************************************************************/
32 /*! Sorts an array of chars in decreasing order */
33 /*************************************************************************/
gk_csortd(size_t n,char * base)34 void gk_csortd(size_t n, char *base)
35 {
36 #define char_gt(a, b) ((*a) > (*b))
37 GK_MKQSORT(char, base, n, char_gt);
38 #undef char_gt
39 }
40
41
42 /*************************************************************************/
43 /*! Sorts an array of integers in increasing order */
44 /*************************************************************************/
gk_isorti(size_t n,int * base)45 void gk_isorti(size_t n, int *base)
46 {
47 #define int_lt(a, b) ((*a) < (*b))
48 GK_MKQSORT(int, base, n, int_lt);
49 #undef int_lt
50 }
51
52
53 /*************************************************************************/
54 /*! Sorts an array of integers in decreasing order */
55 /*************************************************************************/
gk_isortd(size_t n,int * base)56 void gk_isortd(size_t n, int *base)
57 {
58 #define int_gt(a, b) ((*a) > (*b))
59 GK_MKQSORT(int, base, n, int_gt);
60 #undef int_gt
61 }
62
63
64 /*************************************************************************/
65 /*! Sorts an array of floats in increasing order */
66 /*************************************************************************/
gk_fsorti(size_t n,float * base)67 void gk_fsorti(size_t n, float *base)
68 {
69 #define float_lt(a, b) ((*a) < (*b))
70 GK_MKQSORT(float, base, n, float_lt);
71 #undef float_lt
72 }
73
74
75 /*************************************************************************/
76 /*! Sorts an array of floats in decreasing order */
77 /*************************************************************************/
gk_fsortd(size_t n,float * base)78 void gk_fsortd(size_t n, float *base)
79 {
80 #define float_gt(a, b) ((*a) > (*b))
81 GK_MKQSORT(float, base, n, float_gt);
82 #undef float_gt
83 }
84
85
86 /*************************************************************************/
87 /*! Sorts an array of doubles in increasing order */
88 /*************************************************************************/
gk_dsorti(size_t n,double * base)89 void gk_dsorti(size_t n, double *base)
90 {
91 #define double_lt(a, b) ((*a) < (*b))
92 GK_MKQSORT(double, base, n, double_lt);
93 #undef double_lt
94 }
95
96
97 /*************************************************************************/
98 /*! Sorts an array of doubles in decreasing order */
99 /*************************************************************************/
gk_dsortd(size_t n,double * base)100 void gk_dsortd(size_t n, double *base)
101 {
102 #define double_gt(a, b) ((*a) > (*b))
103 GK_MKQSORT(double, base, n, double_gt);
104 #undef double_gt
105 }
106
107
108 /*************************************************************************/
109 /*! Sorts an array of gk_idx_t in increasing order */
110 /*************************************************************************/
gk_idxsorti(size_t n,gk_idx_t * base)111 void gk_idxsorti(size_t n, gk_idx_t *base)
112 {
113 #define idx_lt(a, b) ((*a) < (*b))
114 GK_MKQSORT(gk_idx_t, base, n, idx_lt);
115 #undef idx_lt
116 }
117
118
119 /*************************************************************************/
120 /*! Sorts an array of gk_idx_t in decreasing order */
121 /*************************************************************************/
gk_idxsortd(size_t n,gk_idx_t * base)122 void gk_idxsortd(size_t n, gk_idx_t *base)
123 {
124 #define idx_gt(a, b) ((*a) > (*b))
125 GK_MKQSORT(gk_idx_t, base, n, idx_gt);
126 #undef idx_gt
127 }
128
129
130
131
132 /*************************************************************************/
133 /*! Sorts an array of gk_ckv_t in increasing order */
134 /*************************************************************************/
gk_ckvsorti(size_t n,gk_ckv_t * base)135 void gk_ckvsorti(size_t n, gk_ckv_t *base)
136 {
137 #define ckey_lt(a, b) ((a)->key < (b)->key)
138 GK_MKQSORT(gk_ckv_t, base, n, ckey_lt);
139 #undef ckey_lt
140 }
141
142
143 /*************************************************************************/
144 /*! Sorts an array of gk_ckv_t in decreasing order */
145 /*************************************************************************/
gk_ckvsortd(size_t n,gk_ckv_t * base)146 void gk_ckvsortd(size_t n, gk_ckv_t *base)
147 {
148 #define ckey_gt(a, b) ((a)->key > (b)->key)
149 GK_MKQSORT(gk_ckv_t, base, n, ckey_gt);
150 #undef ckey_gt
151 }
152
153
154 /*************************************************************************/
155 /*! Sorts an array of gk_ikv_t in increasing order */
156 /*************************************************************************/
gk_ikvsorti(size_t n,gk_ikv_t * base)157 void gk_ikvsorti(size_t n, gk_ikv_t *base)
158 {
159 #define ikey_lt(a, b) ((a)->key < (b)->key)
160 GK_MKQSORT(gk_ikv_t, base, n, ikey_lt);
161 #undef ikey_lt
162 }
163
164
165 /*************************************************************************/
166 /*! Sorts an array of gk_ikv_t in decreasing order */
167 /*************************************************************************/
gk_ikvsortd(size_t n,gk_ikv_t * base)168 void gk_ikvsortd(size_t n, gk_ikv_t *base)
169 {
170 #define ikey_gt(a, b) ((a)->key > (b)->key)
171 GK_MKQSORT(gk_ikv_t, base, n, ikey_gt);
172 #undef ikey_gt
173 }
174
175
176 /*************************************************************************/
177 /*! Sorts an array of gk_i32kv_t in increasing order */
178 /*************************************************************************/
gk_i32kvsorti(size_t n,gk_i32kv_t * base)179 void gk_i32kvsorti(size_t n, gk_i32kv_t *base)
180 {
181 #define ikey_lt(a, b) ((a)->key < (b)->key)
182 GK_MKQSORT(gk_i32kv_t, base, n, ikey_lt);
183 #undef ikey_lt
184 }
185
186
187 /*************************************************************************/
188 /*! Sorts an array of gk_i32kv_t in decreasing order */
189 /*************************************************************************/
gk_i32kvsortd(size_t n,gk_i32kv_t * base)190 void gk_i32kvsortd(size_t n, gk_i32kv_t *base)
191 {
192 #define ikey_gt(a, b) ((a)->key > (b)->key)
193 GK_MKQSORT(gk_i32kv_t, base, n, ikey_gt);
194 #undef ikey_gt
195 }
196
197
198 /*************************************************************************/
199 /*! Sorts an array of gk_i64kv_t in increasing order */
200 /*************************************************************************/
gk_i64kvsorti(size_t n,gk_i64kv_t * base)201 void gk_i64kvsorti(size_t n, gk_i64kv_t *base)
202 {
203 #define ikey_lt(a, b) ((a)->key < (b)->key)
204 GK_MKQSORT(gk_i64kv_t, base, n, ikey_lt);
205 #undef ikey_lt
206 }
207
208
209 /*************************************************************************/
210 /*! Sorts an array of gk_i64kv_t in decreasing order */
211 /*************************************************************************/
gk_i64kvsortd(size_t n,gk_i64kv_t * base)212 void gk_i64kvsortd(size_t n, gk_i64kv_t *base)
213 {
214 #define ikey_gt(a, b) ((a)->key > (b)->key)
215 GK_MKQSORT(gk_i64kv_t, base, n, ikey_gt);
216 #undef ikey_gt
217 }
218
219
220 /*************************************************************************/
221 /*! Sorts an array of gk_zkv_t in increasing order */
222 /*************************************************************************/
gk_zkvsorti(size_t n,gk_zkv_t * base)223 void gk_zkvsorti(size_t n, gk_zkv_t *base)
224 {
225 #define zkey_lt(a, b) ((a)->key < (b)->key)
226 GK_MKQSORT(gk_zkv_t, base, n, zkey_lt);
227 #undef zkey_lt
228 }
229
230
231 /*************************************************************************/
232 /*! Sorts an array of gk_zkv_t in decreasing order */
233 /*************************************************************************/
gk_zkvsortd(size_t n,gk_zkv_t * base)234 void gk_zkvsortd(size_t n, gk_zkv_t *base)
235 {
236 #define zkey_gt(a, b) ((a)->key > (b)->key)
237 GK_MKQSORT(gk_zkv_t, base, n, zkey_gt);
238 #undef zkey_gt
239 }
240
241
242 /*************************************************************************/
243 /*! Sorts an array of gk_fkv_t in increasing order */
244 /*************************************************************************/
gk_fkvsorti(size_t n,gk_fkv_t * base)245 void gk_fkvsorti(size_t n, gk_fkv_t *base)
246 {
247 #define fkey_lt(a, b) ((a)->key < (b)->key)
248 GK_MKQSORT(gk_fkv_t, base, n, fkey_lt);
249 #undef fkey_lt
250 }
251
252
253 /*************************************************************************/
254 /*! Sorts an array of gk_fkv_t in decreasing order */
255 /*************************************************************************/
gk_fkvsortd(size_t n,gk_fkv_t * base)256 void gk_fkvsortd(size_t n, gk_fkv_t *base)
257 {
258 #define fkey_gt(a, b) ((a)->key > (b)->key)
259 GK_MKQSORT(gk_fkv_t, base, n, fkey_gt);
260 #undef fkey_gt
261 }
262
263
264 /*************************************************************************/
265 /*! Sorts an array of gk_dkv_t in increasing order */
266 /*************************************************************************/
gk_dkvsorti(size_t n,gk_dkv_t * base)267 void gk_dkvsorti(size_t n, gk_dkv_t *base)
268 {
269 #define dkey_lt(a, b) ((a)->key < (b)->key)
270 GK_MKQSORT(gk_dkv_t, base, n, dkey_lt);
271 #undef dkey_lt
272 }
273
274
275 /*************************************************************************/
276 /*! Sorts an array of gk_fkv_t in decreasing order */
277 /*************************************************************************/
gk_dkvsortd(size_t n,gk_dkv_t * base)278 void gk_dkvsortd(size_t n, gk_dkv_t *base)
279 {
280 #define dkey_gt(a, b) ((a)->key > (b)->key)
281 GK_MKQSORT(gk_dkv_t, base, n, dkey_gt);
282 #undef dkey_gt
283 }
284
285
286 /*************************************************************************/
287 /*! Sorts an array of gk_skv_t in increasing order */
288 /*************************************************************************/
gk_skvsorti(size_t n,gk_skv_t * base)289 void gk_skvsorti(size_t n, gk_skv_t *base)
290 {
291 #define skey_lt(a, b) (strcmp((a)->key, (b)->key) < 0)
292 GK_MKQSORT(gk_skv_t, base, n, skey_lt);
293 #undef skey_lt
294 }
295
296
297 /*************************************************************************/
298 /*! Sorts an array of gk_skv_t in decreasing order */
299 /*************************************************************************/
gk_skvsortd(size_t n,gk_skv_t * base)300 void gk_skvsortd(size_t n, gk_skv_t *base)
301 {
302 #define skey_gt(a, b) (strcmp((a)->key, (b)->key) > 0)
303 GK_MKQSORT(gk_skv_t, base, n, skey_gt);
304 #undef skey_gt
305 }
306
307
308 /*************************************************************************/
309 /*! Sorts an array of gk_idxkv_t in increasing order */
310 /*************************************************************************/
gk_idxkvsorti(size_t n,gk_idxkv_t * base)311 void gk_idxkvsorti(size_t n, gk_idxkv_t *base)
312 {
313 #define idxkey_lt(a, b) ((a)->key < (b)->key)
314 GK_MKQSORT(gk_idxkv_t, base, n, idxkey_lt);
315 #undef idxkey_lt
316 }
317
318
319 /*************************************************************************/
320 /*! Sorts an array of gk_idxkv_t in decreasing order */
321 /*************************************************************************/
gk_idxkvsortd(size_t n,gk_idxkv_t * base)322 void gk_idxkvsortd(size_t n, gk_idxkv_t *base)
323 {
324 #define idxkey_gt(a, b) ((a)->key > (b)->key)
325 GK_MKQSORT(gk_idxkv_t, base, n, idxkey_gt);
326 #undef idxkey_gt
327 }
328