AceSorting  1.0.0
Sorting algorithms for Arduino including Bubble Sort, Insertion Sort, Selection Sort, Shell Sort (3 versions), Comb Sort (4 versions), Quick Sort (3 versions)
combSort.h
Go to the documentation of this file.
1 /*
2 MIT License
3 
4 Copyright (c) 2021 Brian T. Park
5 
6 Permission is hereby granted, free of charge, to any person obtaining a copy
7 of this software and associated documentation files (the "Software"), to deal
8 in the Software without restriction, including without limitation the rights
9 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10 copies of the Software, and to permit persons to whom the Software is
11 furnished to do so, subject to the following conditions:
12 
13 The above copyright notice and this permission notice shall be included in all
14 copies or substantial portions of the Software.
15 
16 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22 SOFTWARE.
23 */
24 
31 #ifndef ACE_SORTING_COMB_SORT_H
32 #define ACE_SORTING_COMB_SORT_H
33 
34 #include "swap.h"
35 
36 #if ! defined(ACE_SORTING_DIRECT_COMB_SORT)
37 
43  #define ACE_SORTING_DIRECT_COMB_SORT 0
44 #endif
45 
46 namespace ace_sorting {
47 
59 #if ACE_SORTING_DIRECT_COMB_SORT
60 template <typename T>
61 void combSort13(T data[], uint16_t n) {
62  bool swapped = true;
63 
64  uint16_t gap = n;
65  while (swapped || gap > 1) {
66  gap = gap * 10 / 13;
67  if (gap == 0) gap = 1;
68  swapped = false;
69 
70  uint16_t i;
71  uint16_t j;
72  for (i = 0, j = gap; j < n; i++, j++) {
73  if (data[j] < data[i]) {
74  swap(data[i], data[j]);
75  swapped = true;
76  }
77  }
78  }
79 }
80 #else
81 template <typename T>
82 void combSort13(T data[], uint16_t n) {
83  // This lambda expression does not perform any captures, so the compiler will
84  // optimize and inline the less-than expression.
85  auto&& lessThan = [](const T& a, const T& b) -> bool { return a < b; };
86  combSort13(data, n, lessThan);
87 }
88 #endif
89 
97 template <typename T, typename F>
98 void combSort13(T data[], uint16_t n, F&& lessThan) {
99  bool swapped = true;
100 
101  uint16_t gap = n;
102  while (swapped || gap > 1) {
103  gap = gap * 10 / 13;
104  if (gap == 0) gap = 1;
105  swapped = false;
106 
107  uint16_t i;
108  uint16_t j;
109  for (i = 0, j = gap; j < n; i++, j++) {
110  if (lessThan(data[j], data[i])) {
111  swap(data[i], data[j]);
112  swapped = true;
113  }
114  }
115  }
116 }
117 
118 //-----------------------------------------------------------------------------
119 
132 #if ACE_SORTING_DIRECT_COMB_SORT
133 template <typename T>
134 void combSort13m(T data[], uint16_t n) {
135  bool swapped = true;
136 
137  uint16_t gap = n;
138  while (swapped || gap > 1) {
139  gap = gap * 10 / 13;
140  if (gap == 9 || gap == 10) {
141  gap = 11;
142  } else if (gap == 0) {
143  gap = 1;
144  }
145  swapped = false;
146 
147  uint16_t i;
148  uint16_t j;
149  for (i = 0, j = gap; j < n; i++, j++) {
150  if (data[j] < data[i]) {
151  swap(data[i], data[j]);
152  swapped = true;
153  }
154  }
155  }
156 }
157 #else
158 template <typename T>
159 void combSort13m(T data[], uint16_t n) {
160  // This lambda expression does not perform any captures, so the compiler will
161  // optimize and inline the less-than expression.
162  auto&& lessThan = [](const T& a, const T& b) -> bool { return a < b; };
163  combSort13m(data, n, lessThan);
164 }
165 #endif
166 
174 template <typename T, typename F>
175 void combSort13m(T data[], uint16_t n, F&& lessThan) {
176  bool swapped = true;
177 
178  uint16_t gap = n;
179  while (swapped || gap > 1) {
180  gap = gap * 10 / 13;
181  if (gap == 9 || gap == 10) {
182  gap = 11;
183  } else if (gap == 0) {
184  gap = 1;
185  }
186  swapped = false;
187 
188  uint16_t i;
189  uint16_t j;
190  for (i = 0, j = gap; j < n; i++, j++) {
191  if (lessThan(data[j], data[i])) {
192  swap(data[i], data[j]);
193  swapped = true;
194  }
195  }
196  }
197 }
198 
199 //-----------------------------------------------------------------------------
200 
224 #if ACE_SORTING_DIRECT_COMB_SORT
225 template <typename T>
226 void combSort133(T data[], uint16_t n) {
227  bool swapped = true;
228 
229  uint16_t gap = n;
230  while (swapped || gap > 1) {
231  gap = gap * 3 / 4;
232  if (gap == 0) gap = 1;
233  swapped = false;
234 
235  uint16_t i;
236  uint16_t j;
237  for (i = 0, j = gap; j < n; i++, j++) {
238  if (data[j] < data[i]) {
239  swap(data[i], data[j]);
240  swapped = true;
241  }
242  }
243  }
244 }
245 #else
246 template <typename T>
247 void combSort133(T data[], uint16_t n) {
248  // This lambda expression does not perform any captures, so the compiler will
249  // optimize and inline the less-than expression.
250  auto&& lessThan = [](const T& a, const T& b) -> bool { return a < b; };
251  combSort133(data, n, lessThan);
252 }
253 #endif
254 
262 template <typename T, typename F>
263 void combSort133(T data[], uint16_t n, F&& lessThan) {
264  bool swapped = true;
265 
266  uint16_t gap = n;
267  while (swapped || gap > 1) {
268  gap = gap * 3 / 4;
269  if (gap == 0) gap = 1;
270  swapped = false;
271 
272  uint16_t i;
273  uint16_t j;
274  for (i = 0, j = gap; j < n; i++, j++) {
275  if (lessThan(data[j], data[i])) {
276  swap(data[i], data[j]);
277  swapped = true;
278  }
279  }
280  }
281 }
282 
283 //-----------------------------------------------------------------------------
284 
296 #if ACE_SORTING_DIRECT_COMB_SORT
297 template <typename T>
298 void combSort133m(T data[], uint16_t n) {
299  bool swapped = true;
300 
301  uint16_t gap = n;
302  while (swapped || gap > 1) {
303  gap = gap * 3 / 4;
304  if (gap == 9 || gap == 10) {
305  gap = 11;
306  } else if (gap == 0) {
307  gap = 1;
308  }
309  swapped = false;
310 
311  uint16_t i;
312  uint16_t j;
313  for (i = 0, j = gap; j < n; i++, j++) {
314  if (data[j] < data[i]) {
315  swap(data[i], data[j]);
316  swapped = true;
317  }
318  }
319  }
320 }
321 #else
322 template <typename T>
323 void combSort133m(T data[], uint16_t n) {
324  // This lambda expression does not perform any captures, so the compiler will
325  // optimize and inline the less-than expression.
326  auto&& lessThan = [](const T& a, const T& b) -> bool { return a < b; };
327  combSort133m(data, n, lessThan);
328 }
329 #endif
330 
338 template <typename T, typename F>
339 void combSort133m(T data[], uint16_t n, F&& lessThan) {
340  bool swapped = true;
341 
342  uint16_t gap = n;
343  while (swapped || gap > 1) {
344  gap = gap * 3 / 4;
345  if (gap == 9 || gap == 10) {
346  gap = 11;
347  } else if (gap == 0) {
348  gap = 1;
349  }
350  swapped = false;
351 
352  uint16_t i;
353  uint16_t j;
354  for (i = 0, j = gap; j < n; i++, j++) {
355  if (lessThan(data[j], data[i])) {
356  swap(data[i], data[j]);
357  swapped = true;
358  }
359  }
360  }
361 }
362 
363 }
364 
365 #endif
swap.h
ace_sorting::swap
void swap(T &a, T &b)
Swap the parameters.
Definition: swap.h:41
ace_sorting::combSort133
void combSort133(T data[], uint16_t n)
Comb sort using a gap factor of 4/3=1.33 (successive gap is multiplied by 3 / 4).
Definition: combSort.h:247
ace_sorting::combSort13
void combSort13(T data[], uint16_t n)
Comb sort using a gap factor of 1.3 (successive gap is multiplied by 10 / 13).
Definition: combSort.h:82
ace_sorting::combSort133m
void combSort133m(T data[], uint16_t n)
Same as combSort133() but modified so that a gap of 9 or 10 becomes gap=11 so that the final sequence...
Definition: combSort.h:323
ace_sorting::combSort13m
void combSort13m(T data[], uint16_t n)
Same as combSort13() with the modification that if the gap is 9 or 10, it is set to 11,...
Definition: combSort.h:159
Generated by   doxygen 1.8.17