tlx
Loading...
Searching...
No Matches
best.hpp
Go to the documentation of this file.
1/*******************************************************************************
2 * tlx/sort/networks/best.hpp
3 *
4 * Implementation of best known sorting networks for up to sixteen elements.
5 *
6 * Part of tlx - http://panthema.net/tlx
7 *
8 * Copyright (C) 2018-2020 Jasper Marianczuk <jasper.marianczuk@gmail.com>
9 * Copyright (C) 2020 Timo Bingmann <tb@panthema.net>
10 *
11 * All rights reserved. Published under the Boost Software License, Version 1.0
12 ******************************************************************************/
13
14#ifndef TLX_SORT_NETWORKS_BEST_HEADER
15#define TLX_SORT_NETWORKS_BEST_HEADER
16
18
19#include <functional>
20
21namespace tlx {
22
23//! Implementations of sorting networks for up to sixteen elements.
24namespace sort_networks {
25
26//! \addtogroup tlx_sort
27//! \{
28//! \name Implementations of Sorting Networks
29//! \{
30
31//! Implementation of best known sorting networks for up to sixteen elements.
32namespace best {
33
34//! default conditional swap implementation
35template <typename Iterator>
37 std::less<typename std::iterator_traits<Iterator>::value_type> >;
38
39//! sorting network for two elements
40template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
41static void sort2(Iterator a, CSwap cswap = CSwap()) {
42 cswap(a[0], a[1]);
43}
44
45//! sorting network for three elements
46template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
47static void sort3(Iterator a, CSwap cswap = CSwap()) {
48 cswap(a[1], a[2]);
49 cswap(a[0], a[2]);
50 cswap(a[0], a[1]);
51}
52
53//! sorting network for four elements
54template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
55static void sort4(Iterator a, CSwap cswap = CSwap()) {
56 cswap(a[0], a[1]);
57 cswap(a[2], a[3]);
58 cswap(a[0], a[2]);
59 cswap(a[1], a[3]);
60 cswap(a[1], a[2]);
61}
62
63//! sorting network for five elements
64template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
65static void sort5(Iterator a, CSwap cswap = CSwap()) {
66 cswap(a[0], a[1]);
67 cswap(a[3], a[4]);
68 cswap(a[2], a[4]);
69 cswap(a[2], a[3]);
70 cswap(a[0], a[3]);
71 cswap(a[0], a[2]);
72 cswap(a[1], a[4]);
73 cswap(a[1], a[3]);
74 cswap(a[1], a[2]);
75}
76
77//! sorting network for six elements
78template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
79static void sort6(Iterator a, CSwap cswap = CSwap()) {
80 cswap(a[1], a[2]);
81 cswap(a[0], a[2]);
82 cswap(a[0], a[1]);
83 cswap(a[4], a[5]);
84 cswap(a[3], a[5]);
85 cswap(a[3], a[4]);
86 cswap(a[0], a[3]);
87 cswap(a[1], a[4]);
88 cswap(a[2], a[5]);
89 cswap(a[2], a[4]);
90 cswap(a[1], a[3]);
91 cswap(a[2], a[3]);
92}
93
94//! sorting network for seven elements
95template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
96static void sort7(Iterator a, CSwap cswap = CSwap()) {
97 cswap(a[1], a[2]);
98 cswap(a[0], a[2]);
99 cswap(a[0], a[1]);
100 cswap(a[3], a[4]);
101 cswap(a[5], a[6]);
102 cswap(a[3], a[5]);
103 cswap(a[4], a[6]);
104 cswap(a[4], a[5]);
105 cswap(a[0], a[4]);
106 cswap(a[0], a[3]);
107 cswap(a[1], a[5]);
108 cswap(a[2], a[6]);
109 cswap(a[2], a[5]);
110 cswap(a[1], a[3]);
111 cswap(a[2], a[4]);
112 cswap(a[2], a[3]);
113}
114
115//! sorting network for eight elements
116template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
117static void sort8(Iterator a, CSwap cswap = CSwap()) {
118 cswap(a[0], a[1]);
119 cswap(a[2], a[3]);
120 cswap(a[0], a[2]);
121 cswap(a[1], a[3]);
122 cswap(a[1], a[2]);
123 cswap(a[4], a[5]);
124 cswap(a[6], a[7]);
125 cswap(a[4], a[6]);
126 cswap(a[5], a[7]);
127 cswap(a[5], a[6]);
128 cswap(a[0], a[4]);
129 cswap(a[1], a[5]);
130 cswap(a[1], a[4]);
131 cswap(a[2], a[6]);
132 cswap(a[3], a[7]);
133 cswap(a[3], a[6]);
134 cswap(a[2], a[4]);
135 cswap(a[3], a[5]);
136 cswap(a[3], a[4]);
137}
138
139//! sorting network for nine elements
140template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
141static void sort9(Iterator a, CSwap cswap = CSwap()) {
142 cswap(a[0], a[1]);
143 cswap(a[3], a[4]);
144 cswap(a[6], a[7]);
145 cswap(a[1], a[2]);
146 cswap(a[4], a[5]);
147 cswap(a[7], a[8]);
148 cswap(a[0], a[1]);
149 cswap(a[3], a[4]);
150 cswap(a[6], a[7]);
151 cswap(a[0], a[3]);
152 cswap(a[3], a[6]);
153 cswap(a[0], a[3]);
154 cswap(a[1], a[4]);
155 cswap(a[4], a[7]);
156 cswap(a[1], a[4]);
157 cswap(a[2], a[5]);
158 cswap(a[5], a[8]);
159 cswap(a[2], a[5]);
160 cswap(a[1], a[3]);
161 cswap(a[5], a[7]);
162 cswap(a[2], a[6]);
163 cswap(a[4], a[6]);
164 cswap(a[2], a[4]);
165 cswap(a[2], a[3]);
166 cswap(a[5], a[6]);
167}
168
169//! sorting network for ten elements
170template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
171static void sort10(Iterator a, CSwap cswap = CSwap()) {
172 cswap(a[4], a[9]);
173 cswap(a[3], a[8]);
174 cswap(a[2], a[7]);
175 cswap(a[1], a[6]);
176 cswap(a[0], a[5]);
177 cswap(a[1], a[4]);
178 cswap(a[6], a[9]);
179 cswap(a[0], a[3]);
180 cswap(a[5], a[8]);
181 cswap(a[0], a[2]);
182 cswap(a[3], a[6]);
183 cswap(a[7], a[9]);
184 cswap(a[0], a[1]);
185 cswap(a[2], a[4]);
186 cswap(a[5], a[7]);
187 cswap(a[8], a[9]);
188 cswap(a[1], a[2]);
189 cswap(a[4], a[6]);
190 cswap(a[7], a[8]);
191 cswap(a[3], a[5]);
192 cswap(a[2], a[5]);
193 cswap(a[6], a[8]);
194 cswap(a[1], a[3]);
195 cswap(a[4], a[7]);
196 cswap(a[2], a[3]);
197 cswap(a[6], a[7]);
198 cswap(a[3], a[4]);
199 cswap(a[5], a[6]);
200 cswap(a[4], a[5]);
201}
202
203//! sorting network for eleven elements
204template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
205static void sort11(Iterator a, CSwap cswap = CSwap()) {
206 cswap(a[0], a[1]);
207 cswap(a[2], a[3]);
208 cswap(a[4], a[5]);
209 cswap(a[6], a[7]);
210 cswap(a[8], a[9]);
211 cswap(a[1], a[3]);
212 cswap(a[5], a[7]);
213 cswap(a[0], a[2]);
214 cswap(a[4], a[6]);
215 cswap(a[8], a[10]);
216 cswap(a[1], a[2]);
217 cswap(a[5], a[6]);
218 cswap(a[9], a[10]);
219 cswap(a[1], a[5]);
220 cswap(a[6], a[10]);
221 cswap(a[5], a[9]);
222 cswap(a[2], a[6]);
223 cswap(a[1], a[5]);
224 cswap(a[6], a[10]);
225 cswap(a[0], a[4]);
226 cswap(a[3], a[7]);
227 cswap(a[4], a[8]);
228 cswap(a[0], a[4]);
229 cswap(a[1], a[4]);
230 cswap(a[7], a[10]);
231 cswap(a[3], a[8]);
232 cswap(a[2], a[3]);
233 cswap(a[8], a[9]);
234 cswap(a[2], a[4]);
235 cswap(a[7], a[9]);
236 cswap(a[3], a[5]);
237 cswap(a[6], a[8]);
238 cswap(a[3], a[4]);
239 cswap(a[5], a[6]);
240 cswap(a[7], a[8]);
241}
242
243//! sorting network for twelve elements
244template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
245static void sort12(Iterator a, CSwap cswap = CSwap()) {
246 cswap(a[0], a[1]);
247 cswap(a[2], a[3]);
248 cswap(a[4], a[5]);
249 cswap(a[6], a[7]);
250 cswap(a[8], a[9]);
251 cswap(a[10], a[11]);
252 cswap(a[1], a[3]);
253 cswap(a[5], a[7]);
254 cswap(a[9], a[11]);
255 cswap(a[0], a[2]);
256 cswap(a[4], a[6]);
257 cswap(a[8], a[10]);
258 cswap(a[1], a[2]);
259 cswap(a[5], a[6]);
260 cswap(a[9], a[10]);
261 cswap(a[1], a[5]);
262 cswap(a[6], a[10]);
263 cswap(a[5], a[9]);
264 cswap(a[2], a[6]);
265 cswap(a[1], a[5]);
266 cswap(a[6], a[10]);
267 cswap(a[0], a[4]);
268 cswap(a[7], a[11]);
269 cswap(a[3], a[7]);
270 cswap(a[4], a[8]);
271 cswap(a[0], a[4]);
272 cswap(a[7], a[11]);
273 cswap(a[1], a[4]);
274 cswap(a[7], a[10]);
275 cswap(a[3], a[8]);
276 cswap(a[2], a[3]);
277 cswap(a[8], a[9]);
278 cswap(a[2], a[4]);
279 cswap(a[7], a[9]);
280 cswap(a[3], a[5]);
281 cswap(a[6], a[8]);
282 cswap(a[3], a[4]);
283 cswap(a[5], a[6]);
284 cswap(a[7], a[8]);
285}
286
287//! sorting network for thirteen elements
288template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
289static void sort13(Iterator a, CSwap cswap = CSwap()) {
290 cswap(a[1], a[7]);
291 cswap(a[9], a[11]);
292 cswap(a[3], a[4]);
293 cswap(a[5], a[8]);
294 cswap(a[0], a[12]);
295 cswap(a[2], a[6]);
296 cswap(a[0], a[1]);
297 cswap(a[2], a[3]);
298 cswap(a[4], a[6]);
299 cswap(a[8], a[11]);
300 cswap(a[7], a[12]);
301 cswap(a[5], a[9]);
302 cswap(a[0], a[2]);
303 cswap(a[3], a[7]);
304 cswap(a[10], a[11]);
305 cswap(a[1], a[4]);
306 cswap(a[6], a[12]);
307 cswap(a[7], a[8]);
308 cswap(a[11], a[12]);
309 cswap(a[4], a[9]);
310 cswap(a[6], a[10]);
311 cswap(a[3], a[4]);
312 cswap(a[5], a[6]);
313 cswap(a[8], a[9]);
314 cswap(a[10], a[11]);
315 cswap(a[1], a[7]);
316 cswap(a[2], a[6]);
317 cswap(a[9], a[11]);
318 cswap(a[1], a[3]);
319 cswap(a[4], a[7]);
320 cswap(a[8], a[10]);
321 cswap(a[0], a[5]);
322 cswap(a[2], a[5]);
323 cswap(a[6], a[8]);
324 cswap(a[9], a[10]);
325 cswap(a[1], a[2]);
326 cswap(a[3], a[5]);
327 cswap(a[7], a[8]);
328 cswap(a[4], a[6]);
329 cswap(a[2], a[3]);
330 cswap(a[4], a[5]);
331 cswap(a[6], a[7]);
332 cswap(a[8], a[9]);
333 cswap(a[3], a[4]);
334 cswap(a[5], a[6]);
335}
336
337//! sorting network for fourteen elements
338template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
339static void sort14(Iterator a, CSwap cswap = CSwap()) {
340 cswap(a[0], a[1]);
341 cswap(a[2], a[3]);
342 cswap(a[4], a[5]);
343 cswap(a[6], a[7]);
344 cswap(a[8], a[9]);
345 cswap(a[10], a[11]);
346 cswap(a[12], a[13]);
347 cswap(a[0], a[2]);
348 cswap(a[4], a[6]);
349 cswap(a[8], a[10]);
350 cswap(a[1], a[3]);
351 cswap(a[5], a[7]);
352 cswap(a[9], a[11]);
353 cswap(a[0], a[4]);
354 cswap(a[8], a[12]);
355 cswap(a[1], a[5]);
356 cswap(a[9], a[13]);
357 cswap(a[2], a[6]);
358 cswap(a[3], a[7]);
359 cswap(a[0], a[8]);
360 cswap(a[1], a[9]);
361 cswap(a[2], a[10]);
362 cswap(a[3], a[11]);
363 cswap(a[4], a[12]);
364 cswap(a[5], a[13]);
365 cswap(a[5], a[10]);
366 cswap(a[6], a[9]);
367 cswap(a[3], a[12]);
368 cswap(a[7], a[11]);
369 cswap(a[1], a[2]);
370 cswap(a[4], a[8]);
371 cswap(a[1], a[4]);
372 cswap(a[7], a[13]);
373 cswap(a[2], a[8]);
374 cswap(a[2], a[4]);
375 cswap(a[5], a[6]);
376 cswap(a[9], a[10]);
377 cswap(a[11], a[13]);
378 cswap(a[3], a[8]);
379 cswap(a[7], a[12]);
380 cswap(a[6], a[8]);
381 cswap(a[10], a[12]);
382 cswap(a[3], a[5]);
383 cswap(a[7], a[9]);
384 cswap(a[3], a[4]);
385 cswap(a[5], a[6]);
386 cswap(a[7], a[8]);
387 cswap(a[9], a[10]);
388 cswap(a[11], a[12]);
389 cswap(a[6], a[7]);
390 cswap(a[8], a[9]);
391}
392
393//! sorting network for fifteen elements
394template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
395static void sort15(Iterator a, CSwap cswap = CSwap()) {
396 cswap(a[0], a[1]);
397 cswap(a[2], a[3]);
398 cswap(a[4], a[5]);
399 cswap(a[6], a[7]);
400 cswap(a[8], a[9]);
401 cswap(a[10], a[11]);
402 cswap(a[12], a[13]);
403 cswap(a[0], a[2]);
404 cswap(a[4], a[6]);
405 cswap(a[8], a[10]);
406 cswap(a[12], a[14]);
407 cswap(a[1], a[3]);
408 cswap(a[5], a[7]);
409 cswap(a[9], a[11]);
410 cswap(a[0], a[4]);
411 cswap(a[8], a[12]);
412 cswap(a[1], a[5]);
413 cswap(a[9], a[13]);
414 cswap(a[2], a[6]);
415 cswap(a[10], a[14]);
416 cswap(a[3], a[7]);
417 cswap(a[0], a[8]);
418 cswap(a[1], a[9]);
419 cswap(a[2], a[10]);
420 cswap(a[3], a[11]);
421 cswap(a[4], a[12]);
422 cswap(a[5], a[13]);
423 cswap(a[6], a[14]);
424 cswap(a[5], a[10]);
425 cswap(a[6], a[9]);
426 cswap(a[3], a[12]);
427 cswap(a[13], a[14]);
428 cswap(a[7], a[11]);
429 cswap(a[1], a[2]);
430 cswap(a[4], a[8]);
431 cswap(a[1], a[4]);
432 cswap(a[7], a[13]);
433 cswap(a[2], a[8]);
434 cswap(a[11], a[14]);
435 cswap(a[2], a[4]);
436 cswap(a[5], a[6]);
437 cswap(a[9], a[10]);
438 cswap(a[11], a[13]);
439 cswap(a[3], a[8]);
440 cswap(a[7], a[12]);
441 cswap(a[6], a[8]);
442 cswap(a[10], a[12]);
443 cswap(a[3], a[5]);
444 cswap(a[7], a[9]);
445 cswap(a[3], a[4]);
446 cswap(a[5], a[6]);
447 cswap(a[7], a[8]);
448 cswap(a[9], a[10]);
449 cswap(a[11], a[12]);
450 cswap(a[6], a[7]);
451 cswap(a[8], a[9]);
452}
453
454//! sorting network for sixteen elements
455template <typename Iterator, typename CSwap = DefaultCSwap<Iterator> >
456static void sort16(Iterator a, CSwap cswap = CSwap()) {
457 cswap(a[0], a[1]);
458 cswap(a[2], a[3]);
459 cswap(a[4], a[5]);
460 cswap(a[6], a[7]);
461 cswap(a[8], a[9]);
462 cswap(a[10], a[11]);
463 cswap(a[12], a[13]);
464 cswap(a[14], a[15]);
465 cswap(a[0], a[2]);
466 cswap(a[4], a[6]);
467 cswap(a[8], a[10]);
468 cswap(a[12], a[14]);
469 cswap(a[1], a[3]);
470 cswap(a[5], a[7]);
471 cswap(a[9], a[11]);
472 cswap(a[13], a[15]);
473 cswap(a[0], a[4]);
474 cswap(a[8], a[12]);
475 cswap(a[1], a[5]);
476 cswap(a[9], a[13]);
477 cswap(a[2], a[6]);
478 cswap(a[10], a[14]);
479 cswap(a[3], a[7]);
480 cswap(a[11], a[15]);
481 cswap(a[0], a[8]);
482 cswap(a[1], a[9]);
483 cswap(a[2], a[10]);
484 cswap(a[3], a[11]);
485 cswap(a[4], a[12]);
486 cswap(a[5], a[13]);
487 cswap(a[6], a[14]);
488 cswap(a[7], a[15]);
489 cswap(a[5], a[10]);
490 cswap(a[6], a[9]);
491 cswap(a[3], a[12]);
492 cswap(a[13], a[14]);
493 cswap(a[7], a[11]);
494 cswap(a[1], a[2]);
495 cswap(a[4], a[8]);
496 cswap(a[1], a[4]);
497 cswap(a[7], a[13]);
498 cswap(a[2], a[8]);
499 cswap(a[11], a[14]);
500 cswap(a[2], a[4]);
501 cswap(a[5], a[6]);
502 cswap(a[9], a[10]);
503 cswap(a[11], a[13]);
504 cswap(a[3], a[8]);
505 cswap(a[7], a[12]);
506 cswap(a[6], a[8]);
507 cswap(a[10], a[12]);
508 cswap(a[3], a[5]);
509 cswap(a[7], a[9]);
510 cswap(a[3], a[4]);
511 cswap(a[5], a[6]);
512 cswap(a[7], a[8]);
513 cswap(a[9], a[10]);
514 cswap(a[11], a[12]);
515 cswap(a[6], a[7]);
516 cswap(a[8], a[9]);
517}
518
519//! Call best known sorting network for up to sixteen elements with given
520//! comparison method
521template <typename Iterator, typename Comparator =
522 std::less<typename std::iterator_traits<Iterator>::value_type> >
523static void sort(Iterator begin, Iterator end, Comparator cmp = Comparator()) {
524 CS_IfSwap<Comparator> cswap(cmp);
525
526 switch (end - begin) {
527 case 0:
528 break;
529 case 1:
530 break;
531 case 2:
532 sort2(begin, cswap);
533 break;
534 case 3:
535 sort3(begin, cswap);
536 break;
537 case 4:
538 sort4(begin, cswap);
539 break;
540 case 5:
541 sort5(begin, cswap);
542 break;
543 case 6:
544 sort6(begin, cswap);
545 break;
546 case 7:
547 sort7(begin, cswap);
548 break;
549 case 8:
550 sort8(begin, cswap);
551 break;
552 case 9:
553 sort9(begin, cswap);
554 break;
555 case 10:
556 sort10(begin, cswap);
557 break;
558 case 11:
559 sort11(begin, cswap);
560 break;
561 case 12:
562 sort12(begin, cswap);
563 break;
564 case 13:
565 sort13(begin, cswap);
566 break;
567 case 14:
568 sort14(begin, cswap);
569 break;
570 case 15:
571 sort15(begin, cswap);
572 break;
573 case 16:
574 sort16(begin, cswap);
575 break;
576 default:
577 abort();
578 break;
579 }
580}
581
582} // namespace best
583
584/******************************************************************************/
585
586//! \}
587//! \}
588
589} // namespace sort_networks
590} // namespace tlx
591
592#endif // !TLX_SORT_NETWORKS_BEST_HEADER
593
594/******************************************************************************/
Conditional swap implementation used for sorting networks: trivial portable C++ implementation with c...
Definition cswap.hpp:33
static void sort5(Iterator a, CSwap cswap=CSwap())
sorting network for five elements
Definition best.hpp:65
static void sort4(Iterator a, CSwap cswap=CSwap())
sorting network for four elements
Definition best.hpp:55
static void sort7(Iterator a, CSwap cswap=CSwap())
sorting network for seven elements
Definition best.hpp:96
static void sort2(Iterator a, CSwap cswap=CSwap())
sorting network for two elements
Definition best.hpp:41
static void sort13(Iterator a, CSwap cswap=CSwap())
sorting network for thirteen elements
Definition best.hpp:289
static void sort8(Iterator a, CSwap cswap=CSwap())
sorting network for eight elements
Definition best.hpp:117
static void sort15(Iterator a, CSwap cswap=CSwap())
sorting network for fifteen elements
Definition best.hpp:395
static void sort9(Iterator a, CSwap cswap=CSwap())
sorting network for nine elements
Definition best.hpp:141
static void sort16(Iterator a, CSwap cswap=CSwap())
sorting network for sixteen elements
Definition best.hpp:456
static void sort12(Iterator a, CSwap cswap=CSwap())
sorting network for twelve elements
Definition best.hpp:245
static void sort10(Iterator a, CSwap cswap=CSwap())
sorting network for ten elements
Definition best.hpp:171
static void sort3(Iterator a, CSwap cswap=CSwap())
sorting network for three elements
Definition best.hpp:47
static void sort14(Iterator a, CSwap cswap=CSwap())
sorting network for fourteen elements
Definition best.hpp:339
static void sort6(Iterator a, CSwap cswap=CSwap())
sorting network for six elements
Definition best.hpp:79
static void sort(Iterator begin, Iterator end, Comparator cmp=Comparator())
Call best known sorting network for up to sixteen elements with given comparison method.
Definition best.hpp:523
static void sort11(Iterator a, CSwap cswap=CSwap())
sorting network for eleven elements
Definition best.hpp:205