MyraMath
network_sort.h
Go to the documentation of this file.
1 // ========================================================================= //
2 // This file is part of MyraMath, copyright (c) 2014-2019 by Ryan A Chilton //
3 // and distributed by MyraCore, LLC. See LICENSE.txt for license terms. //
4 // ========================================================================= //
5 
6 #ifndef MYRAMATH_UTILITY_NETWORK_SORT_H
7 #define MYRAMATH_UTILITY_NETWORK_SORT_H
8 
14 #include <myramath/utility/insertion_sort.h>
15 #include <myramath/utility/eprintf.h>
16 
17 namespace myra {
18 
19 /*
20 template<class T>
21 void network_swap(T* a, T* b)
22  {
23  if (*b < *a)
24  {
25  T t = *a;
26  *b = *a;
27  *a = t;
28  }
29  }
30 */
31 
32 template<class T>
33 void network_swap(T* a, T* b)
34  {
35  if (*b < *a)
36  {
37  T t = *a;
38  *a = *b;
39  *b = t;
40  }
41  }
42 
43 template <class T>
44 void network_sort0(T* p)
45  {
46  }
47 
48 template <class T>
49 void network_sort1(T* p)
50  {
51  }
52 
53 template <class T>
54 void network_sort2(T* p)
55  {
56  network_swap(p+0, p+1);
57  }
58 
59 template <class T>
60 void network_sort3(T* p)
61  {
62  network_swap(p+1, p+2);
63  network_swap(p+0, p+2);
64  network_swap(p+0, p+1);
65  }
66 
67 template <class T>
68 void network_sort4(T* p)
69  {
70  network_swap(p+0, p+1);
71  network_swap(p+2, p+3);
72  network_swap(p+0, p+2);
73  network_swap(p+1, p+3);
74  network_swap(p+1, p+2);
75  }
76 
77 template <class T>
78 void network_sort5(T* p)
79  {
80  network_swap(p+0, p+1);
81  network_swap(p+3, p+4);
82  network_swap(p+2, p+4);
83  network_swap(p+2, p+3);
84  network_swap(p+0, p+3);
85  network_swap(p+0, p+2);
86  network_swap(p+1, p+4);
87  network_swap(p+1, p+3);
88  network_swap(p+1, p+2);
89  }
90 
91 template <class T>
92 void network_sort6(T* p)
93  {
94  network_swap(p+1, p+2);
95  network_swap(p+0, p+2);
96  network_swap(p+0, p+1);
97  network_swap(p+4, p+5);
98  network_swap(p+3, p+5);
99  network_swap(p+3, p+4);
100  network_swap(p+0, p+3);
101  network_swap(p+1, p+4);
102  network_swap(p+2, p+5);
103  network_swap(p+2, p+4);
104  network_swap(p+1, p+3);
105  network_swap(p+2, p+3);
106  }
107 
108 template <class T>
109 void network_sort7(T* p)
110  {
111  network_swap(p+1, p+2);
112  network_swap(p+0, p+2);
113  network_swap(p+0, p+1);
114  network_swap(p+3, p+4);
115  network_swap(p+5, p+6);
116  network_swap(p+3, p+5);
117  network_swap(p+4, p+6);
118  network_swap(p+4, p+5);
119  network_swap(p+0, p+4);
120  network_swap(p+0, p+3);
121  network_swap(p+1, p+5);
122  network_swap(p+2, p+6);
123  network_swap(p+2, p+5);
124  network_swap(p+1, p+3);
125  network_swap(p+2, p+4);
126  network_swap(p+2, p+3);
127  }
128 
129 template <class T>
130 void network_sort8(T* p)
131  {
132  network_swap(p+0, p+1);
133  network_swap(p+2, p+3);
134  network_swap(p+0, p+2);
135  network_swap(p+1, p+3);
136  network_swap(p+1, p+2);
137  network_swap(p+4, p+5);
138  network_swap(p+6, p+7);
139  network_swap(p+4, p+6);
140  network_swap(p+5, p+7);
141  network_swap(p+5, p+6);
142  network_swap(p+0, p+4);
143  network_swap(p+1, p+5);
144  network_swap(p+1, p+4);
145  network_swap(p+2, p+6);
146  network_swap(p+3, p+7);
147  network_swap(p+3, p+6);
148  network_swap(p+2, p+4);
149  network_swap(p+3, p+5);
150  network_swap(p+3, p+4);
151  }
152 
153 template <class T>
154 void network_sort9(T* p)
155  {
156  network_swap(p+0, p+1);
157  network_swap(p+2, p+3);
158  network_swap(p+0, p+2);
159  network_swap(p+1, p+3);
160  network_swap(p+1, p+2);
161  network_swap(p+4, p+5);
162  network_swap(p+7, p+8);
163  network_swap(p+6, p+8);
164  network_swap(p+6, p+7);
165  network_swap(p+4, p+7);
166  network_swap(p+4, p+6);
167  network_swap(p+5, p+8);
168  network_swap(p+5, p+7);
169  network_swap(p+5, p+6);
170  network_swap(p+0, p+5);
171  network_swap(p+0, p+4);
172  network_swap(p+1, p+6);
173  network_swap(p+1, p+5);
174  network_swap(p+1, p+4);
175  network_swap(p+2, p+7);
176  network_swap(p+3, p+8);
177  network_swap(p+3, p+7);
178  network_swap(p+2, p+5);
179  network_swap(p+2, p+4);
180  network_swap(p+3, p+6);
181  network_swap(p+3, p+5);
182  network_swap(p+3, p+4);
183  }
184 
185 template <class T>
186 void network_sort10(T* p)
187  {
188  network_swap(p+0, p+1);
189  network_swap(p+3, p+4);
190  network_swap(p+2, p+4);
191  network_swap(p+2, p+3);
192  network_swap(p+0, p+3);
193  network_swap(p+0, p+2);
194  network_swap(p+1, p+4);
195  network_swap(p+1, p+3);
196  network_swap(p+1, p+2);
197  network_swap(p+5, p+6);
198  network_swap(p+8, p+9);
199  network_swap(p+7, p+9);
200  network_swap(p+7, p+8);
201  network_swap(p+5, p+8);
202  network_swap(p+5, p+7);
203  network_swap(p+6, p+9);
204  network_swap(p+6, p+8);
205  network_swap(p+6, p+7);
206  network_swap(p+0, p+5);
207  network_swap(p+1, p+6);
208  network_swap(p+1, p+5);
209  network_swap(p+2, p+7);
210  network_swap(p+3, p+8);
211  network_swap(p+4, p+9);
212  network_swap(p+4, p+8);
213  network_swap(p+3, p+7);
214  network_swap(p+4, p+7);
215  network_swap(p+2, p+5);
216  network_swap(p+3, p+6);
217  network_swap(p+4, p+6);
218  network_swap(p+3, p+5);
219  network_swap(p+4, p+5);
220  }
221 
222 template <class T>
223 void network_sort11(T* p)
224  {
225  network_swap(p+0, p+1);
226  network_swap(p+3, p+4);
227  network_swap(p+2, p+4);
228  network_swap(p+2, p+3);
229  network_swap(p+0, p+3);
230  network_swap(p+0, p+2);
231  network_swap(p+1, p+4);
232  network_swap(p+1, p+3);
233  network_swap(p+1, p+2);
234  network_swap(p+6, p+7);
235  network_swap(p+5, p+7);
236  network_swap(p+5, p+6);
237  network_swap(p+9, p+10);
238  network_swap(p+8, p+10);
239  network_swap(p+8, p+9);
240  network_swap(p+5, p+8);
241  network_swap(p+6, p+9);
242  network_swap(p+7, p+10);
243  network_swap(p+7, p+9);
244  network_swap(p+6, p+8);
245  network_swap(p+7, p+8);
246  network_swap(p+0, p+6);
247  network_swap(p+0, p+5);
248  network_swap(p+1, p+7);
249  network_swap(p+1, p+6);
250  network_swap(p+1, p+5);
251  network_swap(p+2, p+8);
252  network_swap(p+3, p+9);
253  network_swap(p+4, p+10);
254  network_swap(p+4, p+9);
255  network_swap(p+3, p+8);
256  network_swap(p+4, p+8);
257  network_swap(p+2, p+5);
258  network_swap(p+3, p+6);
259  network_swap(p+4, p+7);
260  network_swap(p+4, p+6);
261  network_swap(p+3, p+5);
262  network_swap(p+4, p+5);
263  }
264 
265 template <class T>
266 void network_sort12(T* p)
267  {
268  network_swap(p+1, p+2);
269  network_swap(p+0, p+2);
270  network_swap(p+0, p+1);
271  network_swap(p+4, p+5);
272  network_swap(p+3, p+5);
273  network_swap(p+3, p+4);
274  network_swap(p+0, p+3);
275  network_swap(p+1, p+4);
276  network_swap(p+2, p+5);
277  network_swap(p+2, p+4);
278  network_swap(p+1, p+3);
279  network_swap(p+2, p+3);
280  network_swap(p+7, p+8);
281  network_swap(p+6, p+8);
282  network_swap(p+6, p+7);
283  network_swap(p+10, p+11);
284  network_swap(p+9, p+11);
285  network_swap(p+9, p+10);
286  network_swap(p+6, p+9);
287  network_swap(p+7, p+10);
288  network_swap(p+8, p+11);
289  network_swap(p+8, p+10);
290  network_swap(p+7, p+9);
291  network_swap(p+8, p+9);
292  network_swap(p+0, p+6);
293  network_swap(p+1, p+7);
294  network_swap(p+2, p+8);
295  network_swap(p+2, p+7);
296  network_swap(p+1, p+6);
297  network_swap(p+2, p+6);
298  network_swap(p+3, p+9);
299  network_swap(p+4, p+10);
300  network_swap(p+5, p+11);
301  network_swap(p+5, p+10);
302  network_swap(p+4, p+9);
303  network_swap(p+5, p+9);
304  network_swap(p+3, p+6);
305  network_swap(p+4, p+7);
306  network_swap(p+5, p+8);
307  network_swap(p+5, p+7);
308  network_swap(p+4, p+6);
309  network_swap(p+5, p+6);
310  }
311 
312 template <class T>
313 void network_sort13(T* p)
314  {
315  network_swap(p+1, p+2);
316  network_swap(p+0, p+2);
317  network_swap(p+0, p+1);
318  network_swap(p+4, p+5);
319  network_swap(p+3, p+5);
320  network_swap(p+3, p+4);
321  network_swap(p+0, p+3);
322  network_swap(p+1, p+4);
323  network_swap(p+2, p+5);
324  network_swap(p+2, p+4);
325  network_swap(p+1, p+3);
326  network_swap(p+2, p+3);
327  network_swap(p+7, p+8);
328  network_swap(p+6, p+8);
329  network_swap(p+6, p+7);
330  network_swap(p+9, p+10);
331  network_swap(p+11, p+12);
332  network_swap(p+9, p+11);
333  network_swap(p+10, p+12);
334  network_swap(p+10, p+11);
335  network_swap(p+6, p+10);
336  network_swap(p+6, p+9);
337  network_swap(p+7, p+11);
338  network_swap(p+8, p+12);
339  network_swap(p+8, p+11);
340  network_swap(p+7, p+9);
341  network_swap(p+8, p+10);
342  network_swap(p+8, p+9);
343  network_swap(p+0, p+7);
344  network_swap(p+0, p+6);
345  network_swap(p+1, p+8);
346  network_swap(p+2, p+9);
347  network_swap(p+2, p+8);
348  network_swap(p+1, p+6);
349  network_swap(p+2, p+7);
350  network_swap(p+2, p+6);
351  network_swap(p+3, p+10);
352  network_swap(p+4, p+11);
353  network_swap(p+5, p+12);
354  network_swap(p+5, p+11);
355  network_swap(p+4, p+10);
356  network_swap(p+5, p+10);
357  network_swap(p+3, p+7);
358  network_swap(p+3, p+6);
359  network_swap(p+4, p+8);
360  network_swap(p+5, p+9);
361  network_swap(p+5, p+8);
362  network_swap(p+4, p+6);
363  network_swap(p+5, p+7);
364  network_swap(p+5, p+6);
365  }
366 
367 template <class T>
368 void network_sort14(T* p)
369  {
370  network_swap(p+1, p+2);
371  network_swap(p+0, p+2);
372  network_swap(p+0, p+1);
373  network_swap(p+3, p+4);
374  network_swap(p+5, p+6);
375  network_swap(p+3, p+5);
376  network_swap(p+4, p+6);
377  network_swap(p+4, p+5);
378  network_swap(p+0, p+4);
379  network_swap(p+0, p+3);
380  network_swap(p+1, p+5);
381  network_swap(p+2, p+6);
382  network_swap(p+2, p+5);
383  network_swap(p+1, p+3);
384  network_swap(p+2, p+4);
385  network_swap(p+2, p+3);
386  network_swap(p+8, p+9);
387  network_swap(p+7, p+9);
388  network_swap(p+7, p+8);
389  network_swap(p+10, p+11);
390  network_swap(p+12, p+13);
391  network_swap(p+10, p+12);
392  network_swap(p+11, p+13);
393  network_swap(p+11, p+12);
394  network_swap(p+7, p+11);
395  network_swap(p+7, p+10);
396  network_swap(p+8, p+12);
397  network_swap(p+9, p+13);
398  network_swap(p+9, p+12);
399  network_swap(p+8, p+10);
400  network_swap(p+9, p+11);
401  network_swap(p+9, p+10);
402  network_swap(p+0, p+7);
403  network_swap(p+1, p+8);
404  network_swap(p+2, p+9);
405  network_swap(p+2, p+8);
406  network_swap(p+1, p+7);
407  network_swap(p+2, p+7);
408  network_swap(p+3, p+10);
409  network_swap(p+4, p+11);
410  network_swap(p+4, p+10);
411  network_swap(p+5, p+12);
412  network_swap(p+6, p+13);
413  network_swap(p+6, p+12);
414  network_swap(p+5, p+10);
415  network_swap(p+6, p+11);
416  network_swap(p+6, p+10);
417  network_swap(p+3, p+7);
418  network_swap(p+4, p+8);
419  network_swap(p+4, p+7);
420  network_swap(p+5, p+9);
421  network_swap(p+6, p+9);
422  network_swap(p+5, p+7);
423  network_swap(p+6, p+8);
424  network_swap(p+6, p+7);
425  }
426 
427 template <class T>
428 void network_sort15(T* p)
429  {
430  network_swap(p+1, p+2);
431  network_swap(p+0, p+2);
432  network_swap(p+0, p+1);
433  network_swap(p+3, p+4);
434  network_swap(p+5, p+6);
435  network_swap(p+3, p+5);
436  network_swap(p+4, p+6);
437  network_swap(p+4, p+5);
438  network_swap(p+0, p+4);
439  network_swap(p+0, p+3);
440  network_swap(p+1, p+5);
441  network_swap(p+2, p+6);
442  network_swap(p+2, p+5);
443  network_swap(p+1, p+3);
444  network_swap(p+2, p+4);
445  network_swap(p+2, p+3);
446  network_swap(p+7, p+8);
447  network_swap(p+9, p+10);
448  network_swap(p+7, p+9);
449  network_swap(p+8, p+10);
450  network_swap(p+8, p+9);
451  network_swap(p+11, p+12);
452  network_swap(p+13, p+14);
453  network_swap(p+11, p+13);
454  network_swap(p+12, p+14);
455  network_swap(p+12, p+13);
456  network_swap(p+7, p+11);
457  network_swap(p+8, p+12);
458  network_swap(p+8, p+11);
459  network_swap(p+9, p+13);
460  network_swap(p+10, p+14);
461  network_swap(p+10, p+13);
462  network_swap(p+9, p+11);
463  network_swap(p+10, p+12);
464  network_swap(p+10, p+11);
465  network_swap(p+0, p+8);
466  network_swap(p+0, p+7);
467  network_swap(p+1, p+9);
468  network_swap(p+2, p+10);
469  network_swap(p+2, p+9);
470  network_swap(p+1, p+7);
471  network_swap(p+2, p+8);
472  network_swap(p+2, p+7);
473  network_swap(p+3, p+11);
474  network_swap(p+4, p+12);
475  network_swap(p+4, p+11);
476  network_swap(p+5, p+13);
477  network_swap(p+6, p+14);
478  network_swap(p+6, p+13);
479  network_swap(p+5, p+11);
480  network_swap(p+6, p+12);
481  network_swap(p+6, p+11);
482  network_swap(p+3, p+7);
483  network_swap(p+4, p+8);
484  network_swap(p+4, p+7);
485  network_swap(p+5, p+9);
486  network_swap(p+6, p+10);
487  network_swap(p+6, p+9);
488  network_swap(p+5, p+7);
489  network_swap(p+6, p+8);
490  network_swap(p+6, p+7);
491  }
492 
493 template <class T>
494 void network_sort16(T* p)
495  {
496  network_swap(p+0, p+1);
497  network_swap(p+2, p+3);
498  network_swap(p+0, p+2);
499  network_swap(p+1, p+3);
500  network_swap(p+1, p+2);
501  network_swap(p+4, p+5);
502  network_swap(p+6, p+7);
503  network_swap(p+4, p+6);
504  network_swap(p+5, p+7);
505  network_swap(p+5, p+6);
506  network_swap(p+0, p+4);
507  network_swap(p+1, p+5);
508  network_swap(p+1, p+4);
509  network_swap(p+2, p+6);
510  network_swap(p+3, p+7);
511  network_swap(p+3, p+6);
512  network_swap(p+2, p+4);
513  network_swap(p+3, p+5);
514  network_swap(p+3, p+4);
515  network_swap(p+8, p+9);
516  network_swap(p+10, p+11);
517  network_swap(p+8, p+10);
518  network_swap(p+9, p+11);
519  network_swap(p+9, p+10);
520  network_swap(p+12, p+13);
521  network_swap(p+14, p+15);
522  network_swap(p+12, p+14);
523  network_swap(p+13, p+15);
524  network_swap(p+13, p+14);
525  network_swap(p+8, p+12);
526  network_swap(p+9, p+13);
527  network_swap(p+9, p+12);
528  network_swap(p+10, p+14);
529  network_swap(p+11, p+15);
530  network_swap(p+11, p+14);
531  network_swap(p+10, p+12);
532  network_swap(p+11, p+13);
533  network_swap(p+11, p+12);
534  network_swap(p+0, p+8);
535  network_swap(p+1, p+9);
536  network_swap(p+1, p+8);
537  network_swap(p+2, p+10);
538  network_swap(p+3, p+11);
539  network_swap(p+3, p+10);
540  network_swap(p+2, p+8);
541  network_swap(p+3, p+9);
542  network_swap(p+3, p+8);
543  network_swap(p+4, p+12);
544  network_swap(p+5, p+13);
545  network_swap(p+5, p+12);
546  network_swap(p+6, p+14);
547  network_swap(p+7, p+15);
548  network_swap(p+7, p+14);
549  network_swap(p+6, p+12);
550  network_swap(p+7, p+13);
551  network_swap(p+7, p+12);
552  network_swap(p+4, p+8);
553  network_swap(p+5, p+9);
554  network_swap(p+5, p+8);
555  network_swap(p+6, p+10);
556  network_swap(p+7, p+11);
557  network_swap(p+7, p+10);
558  network_swap(p+6, p+8);
559  network_swap(p+7, p+9);
560  network_swap(p+7, p+8);
561  }
562 
563 template <class T>
564 void network_sort(T* p, int n)
565  {
566  switch(n)
567  {
568  case 0: network_sort0(p); break;
569  case 1: network_sort1(p); break;
570  case 2: network_sort2(p); break;
571  case 3: network_sort3(p); break;
572  case 4: network_sort4(p); break;
573  case 5: network_sort5(p); break;
574  case 6: network_sort6(p); break;
575  case 7: network_sort7(p); break;
576  case 8: network_sort8(p); break;
577  case 9: network_sort9(p); break;
578  case 10: network_sort10(p); break;
579  case 11: network_sort11(p); break;
580  case 12: network_sort12(p); break;
581  case 13: network_sort13(p); break;
582  case 14: network_sort14(p); break;
583  case 15: network_sort15(p); break;
584  case 16: network_sort16(p); break;
585  default: insertion_sort(p,n);
586  }
587  }
588 
589 } // namespace myra
590 
591 #endif
insertion_sort.h
Insertion sort for a contiguous range of T&#39;s.
eprintf.h
Returns a std::runtime_error() whose message has been populated using printf()-style formatting...
myra
Definition: syntax.dox:1
myra::insertion_sort
void insertion_sort(T *begin, T *end)
Sorts the T&#39;s within the range [begin,end). Note T must be assignable.
Definition: insertion_sort.h:20
Generated on Sun Aug 4 2024 12:26:05 for MyraMath by   doxygen 1.8.13