YetAnotherCoupler 3.4.0
Loading...
Searching...
No Matches
quicksort.c
Go to the documentation of this file.
1// Copyright (c) 2024 The YAC Authors
2//
3// SPDX-License-Identifier: BSD-3-Clause
4
5#include <stdlib.h>
6#include <string.h>
7
8#include "utils_core.h"
9
10#define YAC_QSORT_ARRAY_TYPE int
11#define YAC_QSORT_INDEX_TYPE int
12#define YAC_QSORT_NAME yac_quicksort_index
13#include "quicksort_template.h"
14#undef YAC_QSORT_NAME
15#undef YAC_QSORT_INDEX_TYPE
16#undef YAC_QSORT_ARRAY_TYPE
17
18#define YAC_QSORT_ARRAY_TYPE yac_int
19#define YAC_QSORT_INDEX_TYPE size_t
20#define YAC_QSORT_NAME yac_quicksort_index_yac_int_size_t
21#include "quicksort_template.h"
22#undef YAC_QSORT_NAME
23#undef YAC_QSORT_INDEX_TYPE
24#undef YAC_QSORT_ARRAY_TYPE
25
26#define YAC_QSORT_ARRAY_TYPE yac_int
27#define YAC_QSORT_INDEX_TYPE yac_int
28#define YAC_QSORT_NAME yac_quicksort_index_yac_int_yac_int
29#include "quicksort_template.h"
30#undef YAC_QSORT_NAME
31#undef YAC_QSORT_INDEX_TYPE
32#undef YAC_QSORT_ARRAY_TYPE
33
34#define YAC_QSORT_ARRAY_TYPE yac_int
35#define YAC_QSORT_INDEX_TYPE uint64_t
36#define YAC_QSORT_NAME yac_quicksort_index_yac_int_uint64_t
37#include "quicksort_template.h"
38#undef YAC_QSORT_NAME
39#undef YAC_QSORT_INDEX_TYPE
40#undef YAC_QSORT_ARRAY_TYPE
41
42#define YAC_QSORT_ARRAY_TYPE yac_int
43#define YAC_QSORT_INDEX_TYPE int
44#define YAC_QSORT_NAME yac_quicksort_index_yac_int_int
45#include "quicksort_template.h"
46#undef YAC_QSORT_NAME
47#undef YAC_QSORT_INDEX_TYPE
48#undef YAC_QSORT_ARRAY_TYPE
49
50#define YAC_QSORT_ARRAY_TYPE size_t
51#define YAC_QSORT_INDEX_TYPE size_t
52#define YAC_QSORT_NAME yac_quicksort_index_size_t_size_t
53#include "quicksort_template.h"
54#undef YAC_QSORT_NAME
55#undef YAC_QSORT_INDEX_TYPE
56#undef YAC_QSORT_ARRAY_TYPE
57
58#define YAC_QSORT_ARRAY_TYPE uint64_t
59#define YAC_QSORT_INDEX_TYPE size_t
60#define YAC_QSORT_NAME yac_quicksort_index_uint64_t_size_t
61#include "quicksort_template.h"
62#undef YAC_QSORT_NAME
63#undef YAC_QSORT_INDEX_TYPE
64#undef YAC_QSORT_ARRAY_TYPE
65
66#define YAC_QSORT_ARRAY_TYPE int
67#define YAC_QSORT_INDEX_TYPE size_t
68#define YAC_QSORT_NAME yac_quicksort_index_int_size_t
69#include "quicksort_template.h"
70#undef YAC_QSORT_NAME
71#undef YAC_QSORT_INDEX_TYPE
72#undef YAC_QSORT_ARRAY_TYPE
73
74#define YAC_QSORT_ARRAY_TYPE size_t
75#define YAC_QSORT_INDEX_TYPE yac_int
76#define YAC_QSORT_NAME yac_quicksort_index_size_t_yac_int
77#include "quicksort_template.h"
78#undef YAC_QSORT_NAME
79#undef YAC_QSORT_INDEX_TYPE
80#undef YAC_QSORT_ARRAY_TYPE
81
82#define YAC_QSORT_ARRAY_TYPE size_t
83#define YAC_QSORT_INDEX_TYPE int
84#define YAC_QSORT_NAME yac_quicksort_index_size_t_int
85#include "quicksort_template.h"
86#undef YAC_QSORT_NAME
87#undef YAC_QSORT_INDEX_TYPE
88#undef YAC_QSORT_ARRAY_TYPE
89
90#define YAC_QSORT_ARRAY_TYPE size_t
91#define YAC_QSORT_INDEX_TYPE void*
92#define YAC_QSORT_NAME yac_quicksort_index_size_t_void_p
93#include "quicksort_template.h"
94#undef YAC_QSORT_NAME
95#undef YAC_QSORT_INDEX_TYPE
96#undef YAC_QSORT_ARRAY_TYPE
97
98#define YAC_QSORT_ARRAY_TYPE int
99#define YAC_QSORT_INDEX_TYPE yac_int
100#define YAC_QSORT_NAME yac_quicksort_index_int_yac_int
101#include "quicksort_template.h"
102#undef YAC_QSORT_NAME
103#undef YAC_QSORT_INDEX_TYPE
104#undef YAC_QSORT_ARRAY_TYPE
105
106#define YAC_QSORT_ARRAY_TYPE int
107#define YAC_QSORT_INDEX_TYPE double
108#define YAC_QSORT_NAME yac_quicksort_index_int_double
109#include "quicksort_template.h"
110#undef YAC_QSORT_NAME
111#undef YAC_QSORT_INDEX_TYPE
112#undef YAC_QSORT_ARRAY_TYPE
113
114#define YAC_QSORT_ARRAY_TYPE_A size_t
115#define YAC_QSORT_ARRAY_TYPE_B size_t
116#define YAC_QSORT_ARRAY_TYPE_C double
117#define YAC_QSORT_NAME yac_quicksort_index_size_t_size_t_double
118#include "quicksort_template_2.h"
119#undef YAC_QSORT_NAME
120#undef YAC_QSORT_ARRAY_TYPE_A
121#undef YAC_QSORT_ARRAY_TYPE_B
122#undef YAC_QSORT_ARRAY_TYPE_C
123
124#define YAC_QSORT_ARRAY_TYPE_A yac_int
125#define YAC_QSORT_ARRAY_TYPE_B yac_int
126#define YAC_QSORT_ARRAY_TYPE_C double
127#define YAC_QSORT_NAME yac_quicksort_index_yac_int_yac_int_double
128#include "quicksort_template_2.h"
129#undef YAC_QSORT_NAME
130#undef YAC_QSORT_ARRAY_TYPE_A
131#undef YAC_QSORT_ARRAY_TYPE_B
132#undef YAC_QSORT_ARRAY_TYPE_C
133
134#define YAC_QSORT_ARRAY_TYPE_A yac_int
135#define YAC_QSORT_ARRAY_TYPE_B yac_int
136#define YAC_QSORT_ARRAY_TYPE_C size_t
137#define YAC_QSORT_NAME yac_quicksort_index_yac_int_yac_int_size_t
138#include "quicksort_template_2.h"
139#undef YAC_QSORT_NAME
140#undef YAC_QSORT_ARRAY_TYPE_A
141#undef YAC_QSORT_ARRAY_TYPE_B
142#undef YAC_QSORT_ARRAY_TYPE_C
143
144#define YAC_QSORT_ARRAY_TYPE_A int
145#define YAC_QSORT_ARRAY_TYPE_B size_t
146#define YAC_QSORT_ARRAY_TYPE_C size_t
147#define YAC_QSORT_NAME yac_quicksort_index_int_size_t_size_t
148#include "quicksort_template_2.h"
149#undef YAC_QSORT_NAME
150#undef YAC_QSORT_ARRAY_TYPE_A
151#undef YAC_QSORT_ARRAY_TYPE_B
152#undef YAC_QSORT_ARRAY_TYPE_C
153
154#define YAC_QSORT_ARRAY_TYPE_A int
155#define YAC_QSORT_ARRAY_TYPE_B size_t
156#define YAC_QSORT_ARRAY_TYPE_C yac_int
157#define YAC_QSORT_NAME yac_quicksort_index_int_size_t_yac_int
158#include "quicksort_template_2.h"
159#undef YAC_QSORT_NAME
160#undef YAC_QSORT_ARRAY_TYPE_A
161#undef YAC_QSORT_ARRAY_TYPE_B
162#undef YAC_QSORT_ARRAY_TYPE_C
163
164#define MAX_STACK_SIZE (64)
185void yac_qsort_index(
186 void * a_, size_t count, size_t size,
187 int (*compare)(void const *, void const *), size_t * idx) {
188
189 if (count < 2) return;
190
191 /* Initialization */
192
193 struct {
194 size_t l, r;
195 } stack[MAX_STACK_SIZE];
196
197 size_t stack_size = 1;
198 stack[0].l = 0;
199 stack[0].r = count-1;
200
201 void * x = xmalloc(2 * size);
202 void * temp = (unsigned char*)x + size;
203 unsigned char * a = a_;
204
205 /* Start sorting
206
207 ... keep taking the top request from the stack until stack_size = 0.
208
209 */
210
211 while ( stack_size > 0 ) {
212
213 stack_size--;
214 size_t l = stack[stack_size].l;
215 size_t r = stack[stack_size].r;
216
217 /* ... keep splitting a[l], ... ,a[r] until l>= r. */
218
219 while ( l < r ) {
220
221 size_t i = l;
222 size_t j = r;
223 memcpy(x, &a[((l+r+1) / 2)*size], size);
224
225 do {
226
227 /* Search from lower end */
228 while(compare(&a[i*size], x) < 0) i++;
229
230 /* Search from upper end */
231 while(compare(x, &a[j*size]) < 0) j--;
232
233 if (i > j) break;
234
235 /* Swap positions i & j */
236
237 memcpy(temp, &a[i*size], size);
238 memcpy(&a[i*size], &a[j*size], size);
239 memcpy(&a[j*size], temp, size);
240
241 if (idx != NULL) {
242 size_t temp_idx = idx[i];
243 idx[i] = idx[j];
244 idx[j] = temp_idx;
245 }
246
247 i++;
248 j--;
249
250 } while (i < j);
251
252 if ( j-l >= r-i ) {
253
254 if ( l < j ) {
255
256 stack[stack_size].l = l;
257 stack[stack_size].r = j;
258 stack_size++;
259 }
260
261 l = i;
262
263 } else {
264
265 if ( i < r ) {
266
267 stack[stack_size].l = i;
268 stack[stack_size].r = r;
269 stack_size++;
270 }
271
272 r = j;
273 }
274 } /* ( l < r ) */
275 } /* ( stack_size /= 0 ) */
276
277 free(x);
278}
279#undef MAX_STACK_SIZE
xmalloc
#define xmalloc(size)
Definition ppm_xfuncs.h:66
yac_qsort_index
void yac_qsort_index(void *a_, size_t count, size_t size, int(*compare)(void const *, void const *), size_t *idx)
Definition quicksort.c:185
MAX_STACK_SIZE
#define MAX_STACK_SIZE
Definition quicksort.c:164
quicksort_template.h
quicksort_template_2.h
utils_core.h
Generated on Mon Sep 16 2024 07:26:17 for YetAnotherCoupler by doxygen 1.11.0